I have a Max Heap implemented using a vector. The trickeUpRec() and trickleDownRec() functions move the vector nodes into their correct positions in order to satisfy the rules for a Max Heap.
I also have a HeapSort() function which should sort a vector of 1000 ints although it gives the incorrect output. Can anyone see why?
I have also templated the class in order to use chars etc.
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
usingnamespace std;
template <typename T>
class Heap
{
private:
vector<T> vec;
// return parent of vec[i] if i is not already a root node
int PARENT(int i)
{
return (i - 1) / 2;
}
// return left child of vec[i]
int LEFT(int i)
{
return (2 * i + 1);
}
// return right child of vec[i]
int RIGHT(int i)
{
return (2 * i + 2);
}
void trickleDownRec(int i)
{
// get left and right child of node at index i
int left = LEFT(i);
int right = RIGHT(i);
int largest = i;
// compare vec[i] with its left and right child
// and find largest value
if (left < vec.size() && vec[left] > vec[i])
largest = left;
if (right < vec.size() && vec[right] > vec[largest])
largest = right;
// swap with child having greater value and
// call heapify-down on the child
if (largest != i) {
swap(vec[i], vec[largest]);
trickleDownRec(largest);
}
}
void trickleUpRec(int i)
{
// check if node at index i and its parent violates
// the heap property
if (i && vec[PARENT(i)] < vec[i])
{
// swap the two if heap property is violated
swap(vec[i], vec[PARENT(i)]);
// call Heapify-up on the parent
trickleUpRec(PARENT(i));
}
}
public:
void heapSort()
{
int n = vec.size();
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(vec[0], vec[i]);
// call max heapify on the reduced heap
trickleDownRec(i);
}
}
void display()
{
for (int i = 0; i < vec.size(); i++)
{
cout << vec.at(i) << ", ";
}
}
// insert key into the heap
void insert(int key)
{
// insert the new element to the end of the vector
vec.push_back(key);
// get element index and call heapify-up procedure
int index = vec.size() - 1;
trickleUpRec(index);
}
// function to remove element with highest priority (present at root)
void remove()
{
try {
// if heap has no elements, throw an exception
if (vec.size() == 0)
throw out_of_range("Vector<X>::at() : ""index is out of range(Heap underflow)");
// replace the root of the heap with the last element
// of the vector
vec[0] = vec.back();
vec.pop_back();
// call heapify-down on root node
trickleDownRec(0);
}
// catch and print the exception
catch (const out_of_range & oor) {
cout << "\n" << oor.what();
}
}
};
int main()
{
Heap<int> pq;
pq.insert(3);
pq.insert(2);
pq.insert(15);
pq.insert(5);
pq.insert(4);
pq.insert(45);
cout << "Max Heap: \n";
pq.display();
pq.remove();
cout << "\n";
pq.display();
Heap<int> pq2;
for (int i = 0; i < 1000; i++)
{
int j = rand() % 1000;
pq2.insert(j);
}
cout << "\nHeap Sort for Vector of 1000 random ints: \n";
pq2.heapSort();
pq2.display();
return 0;
}
void heapSort()
{
int n = vec.size();
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(vec[0], vec[i]);
// call max heapify on the reduced heap
trickleDownRec(i);
}
}
pen and paper and simulate that function.
you say «call max heapify on the reduced heap» but at no point you reduce the heap
the first time you call `trickleDownRec(n-1)', that would do nothing
tricleDown should start at 0, but not going beyond i
void trickleDownRec(int n, int i)
{
// get left and right child of node at index i
int left = LEFT(i);
int right = RIGHT(i);
int largest = i;
// compare vec[i] with its left and right child
// and find largest value
if (left < n && vec[left] > vec[i])
largest = left;
if (right < n && vec[right] > vec[largest])
largest = right;
// swap with child having greater value and
// call heapify-down on the child
if (largest != i) {
swap(vec[i], vec[largest]);
trickleDownRec(n, largest);
}
}
void heapSort()
{
int n = vec.size();
for (int i = n - 1; i >= 0; i--) {
swap(vec[0], vec[i]);
trickleDownRec(i, 0);
}
}
