1

I have written this code after studying from Introduction to Algorithm. I am unable to find out what is the problem with the code. I have written the code for heapsort and it runs well. heap_extract_max() will return the maximum value. heap_increase_key() increase the priority of an element. Here I have written program for priority queue using singly linked list which runs well.

#include <iostream> #include <vector> #include <algorithm> template<typename T> void max_heapify(std::vector<T>& array, size_t index) { size_t largest; size_t left = (2*index) + 1; size_t right = left + 1; if(left < array.size() && array[left] > array[index]) largest = left; else largest = index; if(right < array.size() && array[right] > array[largest]) largest = right; if(largest != index) { int tmp = array[index]; array[index] = array[largest]; array[largest] = tmp; max_heapify(array, largest); } } template<typename T> void build_max_heap(std::vector<T>& array) { for(size_t i = (array.size()/2) - 1; i >= 0; i--) max_heapify(array, i); } template<typename T> T heap_maximum(std::vector<T>& array) { return array[0]; } template<typename T> T heap_extract_max(std::vector<T>& array) { if(array.size() < 0) { std::cerr << "Heap Underflow \n"; } else { T max = array[0]; array[0] = array[array.size() - 1]; //array.size() = array.size() - 1; max_heapify(array, 1); return max; } } template<typename T> void heap_increase_key(std::vector<T>& array, size_t index, T value) { if(value < array[index]) { std::cerr <<"New value is smaller than the current value\n"; return; } else { array[index] = value; while(index > 0 && array[(index/2) - 1] < array[index]) { std::swap(array[index], array[(index/2) - 1]); index = (index/2) - 1; } } } template<typename T> void max_heap_insert(std::vector<T>& array, T value) { array[array.size()] = -1; heap_increase_key(array, array.size(), value); } int main() { std::vector<int> v({1, 2, 6, 3, 7}); build_max_heap(v); std::cout << heap_extract_max(v)<<"\n"; for(size_t i = 0; i < v.size(); i++) { std::cout << v[i] << " "; } std::cout << "\n"; }

It is not showing any output. I am writing commands

$ g++ -std=c++11 priorityqueue.cpp -o priorityqueue $ ./priorityqueue
Improve this question
4
  • Warnings and debugger might mention things like "not all control paths return a value" during the compile, or "subscript out of range" during runtime. Debugging your code is your job, but it's much easier if you use the tools available. Commented Sep 2, 2017 at 17:59
  • How did you figure out that "it's not showing any output"? Maybe does it enter an infinite loop in heap_extract_max()? Try looking at the process list whether your program is still running. Commented Sep 2, 2017 at 18:15
  • y'all are too nice. If you make coder use -Wall and gdb, it will go a lot farther than handing someone a fish. Commented Sep 2, 2017 at 18:32
  • If this is for academia, I can certainly understand the restriction of not using the std::priority_queue container adapter (the obvious choice for eliminating literally all of this code). However, setting that aside, I don't suppose using std::make_heap, std::push_heap, and std::pop_heap are options. It would eliminate nearly all of this code as well. Commented Sep 2, 2017 at 19:21

2 Answers 2

Reset to default
2

Problem is with the below function what will be return for if case because of that

Control may reach end of non-void function

template<typename T> T heap_extract_max(std::vector<T>& array) { if(array.size() < 0) { std::cerr << "Heap Underflow \n"; } else { T max = array[0]; array[0] = array[array.size() - 1]; //array.size() = array.size() - 1; max_heapify(array, 1); return max; } }

Add return -1 or anything else for if case

if(array.size() < 0) { std::cerr << "Heap Underflow \n"; return -1; }

second problem

for(size_t i = (array.size()/2) - 1; i >= 0; i--)

Comparison of unsigned expression >= 0 is always true

Try changing to:(as suggested by Serge Rogatch)

for(int64_t i = (int64_t(array.size())/2) - 1; i >= 0; i--)

As well as there is problem with extracting it Before change result was

7 2 3 6 1 2 Program ended with exit code: 0

Because of wrong handling of remove .Handled removed properly in below code

template<typename T> T heap_extract_max(std::vector<T>& array) { if(array.size() < 0) { std::cerr << "Heap Underflow \n"; return -1; } else { T max = array[0]; array[0] = array[array.size() - 1]; array.erase(std::remove(array.begin(), array.end(), array[0]), array.end()); array.shrink_to_fit(); max_heapify(array, 0); return max; } }

After change

7 6 3 1 2 Program ended with exit code: 0
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

It seems your program enters an infinite loop or crashes. I see a problem here:

for(size_t i = (array.size()/2) - 1; i >= 0; i--)

Because i is unsigned, it is always i >= 0. Also, for array.size() <= 1, you initialize it with some large positive integer, because i tries to go negative, but size_t is never negative, so the number wraps.

Try changing to:

for(int64_t i = (int64_t(array.size())/2) - 1; i >= 0; i--)

Also you seem to confuse 0- and 1-based array indexing, and you should do array.pop_back() in place of //array.size() = array.size() - 1;. Furthermore, it seems you intended array[1] instead of array[0] here:

T max = array[0]; array[0] = array[array.size() - 1];

If you stick with 1-based indexing, you should place and keep a dummy element at index 0 in your array:

std::vector<int> v({/*dummy*/-1, 1, 2, 6, 3, 7});

Array size is never negative, so you don't need if(array.size() < 0) and what's in then clause.

Though 0-based indexing is more natural in C++ and heap can be implemented with it too. For this you would need to revise all the index arithmetic like:

size_t left = (2*index) + 1; size_t right = left + 1;

and

array[(index/2) - 1]
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.