#include <iostream> #include <sstream> using namespace std; class Heap{ public: //Build empty heap Heap(); //Builds a heap from list Heap(int list[], int listSize); //not used for this lab void insert(int x); //removes the smallest element in the heap int remove(); //returns the size of the heap; int size(); private: //heap is implemented as an array of 25 ints //better implementation would be a dynamic array int heap[25]; //number of elements currently in the heap int heapSize; //down heap function void heapify(int location); //up heap function for insert void upheaval(int location); //build heap function used by constructor that takes in array void buildHeap(); int leftChild(int index); int rightChild(int index); int parent(int index); }; Heap::Heap() { heapSize = 0; } Heap::Heap(int list[], int listSize) { //remember heaps start at 1 not zero heap[0]=-1; for(int i=0; i < listSize; i++) { heap[i+1] = list[i]; } heapSize = listSize; buildHeap(); } void Heap::insert(int x) { //location to insert is heapSize+1 //(Recall, 0th location not used) heap[heapSize+1] = x; heapSize++; //heapsize points to index of last element now //reheap upheaval(heapSize); } int Heap::remove() { if (heapSize > 0) { int tmp = heap[0]; heap[0] = heap[--heapSize]; heapify(heapSize - 1); return tmp; } } int Heap::size() { return heapSize; } void Heap::heapify(int location) { int left, right, min; left = leftChild(location); right = rightChild(location); if (left <= heapSize && heap[left] < heap[location]) min = left; else min = location; if (right <= heapSize && heap[right] < heap[min]) min = right; if (min != location) { int t = heap[min]; heap[min] = heap[location]; heap[location] = t; heapify(min); } } void Heap::upheaval(int location) { //coming soon as it gives away the answer to heapify } void Heap::buildHeap() { for (int i = heapSize / 2; i >= 0; i--) { heapify(i); } } int Heap::leftChild(int index) { return index*2; } int Heap::rightChild(int index) { return index*2+1; } int Heap::parent(int index) { return index/2; } //not part of the heap class. but uses a heap void heapSort(int list[], int size) { int* temp; temp = new int[size]; Heap h(list,size); for(int i=0; i < size; i++) { temp[i] = h.remove(); } for(int j=0; j < size; j++) { list[j] = temp[j]; } } int main() { int testList[] = {34, 5, 23, 12, 33, 98, 4, 13, 44, 37, 1, 86, 8}; int size = 13; heapSort(testList, size); cout << "Lists should match " << endl; cout << "1, 4, 5, 8, 12, 13, 23, 33, 34, 37, 44, 86, 98" << endl; for(int i=0; i < size; i++) { cout << testList[i] << ", "; } cout << endl; }

# Minimum Heap

Page 1 of 1## 12 Replies - 42116 Views - Last Post: 13 November 2011 - 08:28 PM

### #1

# Minimum Heap

Posted 13 November 2011 - 04:28 PM

Hi, I am having trouble getting this minimum heap to work properly. I can't get it to print in the proper ascending order. Everything was supplied except for the remove, heapify, and buildHeap functions. I think the problem is in the heapify part, but I can't figure it out. Thanks.

##
**Replies To:** Minimum Heap

### #2

## Re: Minimum Heap

Posted 13 November 2011 - 05:06 PM

I'm interested as to why the first element of the heap isn't used.

Heapify() is correct. I think the problem lies with remove().

In the first line, you access heap[0] but I'm pretty sure heap[0] never gets a value. Because in heapSort(), you have:

In the constructor you fill the backing list, starting at index 1, and then you start calling remove. You never call insert() where heap[0] is written to.

The second line looks fine. In the third line, you can heapify() on the end of list (a leaf), yet you just gave the tree root a new value (which is possibly not the smallest value in the heap) in the second line. You should call heapify on the tree root: heapify(0) or heapfiy(1) in your case.

//remember heaps start at 1 not zero heap[0]=-1; for(int i=0; i < listSize; i++) { heap[i+1] = list[i]; }

Heapify() is correct. I think the problem lies with remove().

int tmp = heap[0]; heap[0] = heap[--heapSize]; heapify(heapSize - 1);

In the first line, you access heap[0] but I'm pretty sure heap[0] never gets a value. Because in heapSort(), you have:

Heap h(list,size); for(int i=0; i < size; i++) { temp[i] = h.remove(); }

In the constructor you fill the backing list, starting at index 1, and then you start calling remove. You never call insert() where heap[0] is written to.

The second line looks fine. In the third line, you can heapify() on the end of list (a leaf), yet you just gave the tree root a new value (which is possibly not the smallest value in the heap) in the second line. You should call heapify on the tree root: heapify(0) or heapfiy(1) in your case.

### #3

## Re: Minimum Heap

Posted 13 November 2011 - 05:27 PM

I was able to fix your sort. Just get rid of

in the constructor, change the for loop to:

and call heapify(0) in remove().

heap[0]=-1;

in the constructor, change the for loop to:

for(int i=0; i < listSize; i++) heap[i] = list[i];

and call heapify(0) in remove().

### #4

## Re: Minimum Heap

Posted 13 November 2011 - 05:47 PM

Ok, I made those changes and it almost works. But now it has everything right but the end it has 86, 86 instead of 86, 98.

I'm not allowed to change anything but remove, heapify, and buildHeap. So I can't change the constructor.

I'm not allowed to change anything but remove, heapify, and buildHeap. So I can't change the constructor.

### #5

## Re: Minimum Heap

Posted 13 November 2011 - 06:08 PM

I got it to work with exactly those changes. Lets see your updated code.

Ah...you should be able to adapt the code. Leave the changes, and change the code to treat heap[i] as heap[i-1].

**Edit:**Quote

I'm not allowed to change anything but remove, heapify, and buildHeap. So I can't change the constructor.

Ah...you should be able to adapt the code. Leave the changes, and change the code to treat heap[i] as heap[i-1].

This post has been edited by **blackcompe**: 13 November 2011 - 06:13 PM

### #6

## Re: Minimum Heap

Posted 13 November 2011 - 06:14 PM

I'm not exactly sure where you mean, this is my current code.

#include <iostream> #include <sstream> using namespace std; class Heap{ public: //Build empty heap Heap(); //Builds a heap from list Heap(int list[], int listSize); //not used for this lab void insert(int x); //removes the smallest element in the heap int remove(); //returns the size of the heap; int size(); private: //heap is implemented as an array of 25 ints //better implementation would be a dynamic array int heap[25]; //number of elements currently in the heap int heapSize; //down heap function void heapify(int location); //up heap function for insert void upheaval(int location); //build heap function used by constructor that takes in array void buildHeap(); int leftChild(int index); int rightChild(int index); int parent(int index); }; Heap::Heap() { heapSize = 0; } Heap::Heap(int list[], int listSize) { //remember heaps start at 1 not zero heap[0]=-1; for(int i=0; i < listSize; i++) { heap[i+1] = list[i]; } heapSize = listSize; buildHeap(); } void Heap::insert(int x) { //location to insert is heapSize+1 //(Recall, 0th location not used) heap[heapSize+1] = x; heapSize++; //heapsize points to index of last element now //reheap upheaval(heapSize); } int Heap::remove() { if (heapSize > 0) { int tmp = heap[1]; heap[1] = heap[--heapSize]; heapify(1); return tmp; } } int Heap::size() { return heapSize; } void Heap::heapify(int location) { int left, right, min; left = leftChild(location); right = rightChild(location); if (left <= heapSize && heap[left] < heap[location]) min = left; else min = location; if (right <= heapSize && heap[right] < heap[min]) min = right; if (min != location) { int t = heap[min]; heap[min] = heap[location]; heap[location] = t; heapify(min); } } void Heap::upheaval(int location) { //coming soon as it gives away the answer to heapify } void Heap::buildHeap() { for (int i = (heapSize + 1) / 2; i >= 0; i--) { heapify(i); } } int Heap::leftChild(int index) { return index*2; } int Heap::rightChild(int index) { return index*2+1; } int Heap::parent(int index) { return index/2; } //not part of the heap class. but uses a heap void heapSort(int list[], int size) { int* temp; temp = new int[size]; Heap h(list,size); for(int i=0; i < size; i++) { temp[i] = h.remove(); } for(int j=0; j < size; j++) { list[j] = temp[j]; } } int main() { int testList[] = {34, 5, 23, 12, 33, 98, 4, 13, 44, 37, 1, 86, 8}; int size = 13; heapSort(testList, size); cout << "Lists should match " << endl; cout << "1, 4, 5, 8, 12, 13, 23, 33, 34, 37, 44, 86, 98" << endl; for(int i=0; i < size; i++) { cout << testList[i] << ", "; } cout << endl; }

### #7

## Re: Minimum Heap

Posted 13 November 2011 - 06:17 PM

You should add a check to make sure the input size is < 25, because this can throw a seg fault (index out of bounds error).

If sizeof(list) == 25 and sizeof(heap) == 25, you'll be writing into heap from indices 1 ... 25. Just a thought. Not really important at this point.

heap[0] = -1; for(int i=0; i < listSize; i++) heap[i+1] = list[i];

If sizeof(list) == 25 and sizeof(heap) == 25, you'll be writing into heap from indices 1 ... 25. Just a thought. Not really important at this point.

### #8

## Re: Minimum Heap

Posted 13 November 2011 - 06:32 PM

Try using this to debug your program:

98 is lost.

Heap::Heap(int list[], int listSize) { //remember heaps start at 1 not zero heap[0]=-1; for(int i=0; i < listSize; i++) { heap[i+1] = list[i]; } heapSize = listSize; cout<<"Before build heap: "; for(int i=0; i < listSize; i++) { cout<<heap[i]<<" "; } cout<<endl; buildHeap(); cout<<"After build heap: "; for(int i=0; i < listSize; i++) { cout<<heap[i]<<" "; } cout<<endl; }

98 is lost.

This post has been edited by **blackcompe**: 13 November 2011 - 06:34 PM

### #9

## Re: Minimum Heap

Posted 13 November 2011 - 06:44 PM

And 8 doesn't seem to make it into the heap.

Ha...nevermind. They're both there.

Needs to be post-increment. That will fix it.

Ha...nevermind. They're both there.

heap[1] = heap[heapSize--];

Needs to be post-increment. That will fix it.

This post has been edited by **blackcompe**: 13 November 2011 - 06:44 PM

### #10

## Re: Minimum Heap

Posted 13 November 2011 - 06:54 PM

You should also test you sort with 24 ints to see it works and then fails with 25, because of what I was saying earlier (not using heap[0]). So you should add some kind of check to let the user know input must be < 25.

### #11

## Re: Minimum Heap

Posted 13 November 2011 - 08:16 PM

Thank you so much! That post decrement was the trick. I will put in a check and everything. Thanks again!

### #13

## Re: Minimum Heap

Posted 13 November 2011 - 08:28 PM

you know what's really cool? the standard library

std::make_heap can do this all for you!

edit:

you can also change the predicate to achieve a max heap

std::make_heap can do this all for you!

edit:

you can also change the predicate to achieve a max heap

This post has been edited by **ishkabible**: 13 November 2011 - 08:28 PM

Page 1 of 1