12 Replies - 42116 Views - Last Post: 13 November 2011 - 08:28 PM Rate Topic: -----

#1 defiant91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 13-November 11

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.
#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;
	
	
}



Is This A Good Question/Topic? 0
  • +

Replies To: Minimum Heap

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

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.

//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.
Was This Post Helpful? 1
  • +
  • -

#3 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Re: Minimum Heap

Posted 13 November 2011 - 05:27 PM

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

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().
Was This Post Helpful? 0
  • +
  • -

#4 defiant91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 13-November 11

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.
Was This Post Helpful? 0
  • +
  • -

#5 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Re: Minimum Heap

Posted 13 November 2011 - 06:08 PM

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

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

Was This Post Helpful? 0
  • +
  • -

#6 defiant91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 13-November 11

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;
	
	
}


Was This Post Helpful? 0
  • +
  • -

#7 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

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).

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.
Was This Post Helpful? 0
  • +
  • -

#8 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Re: Minimum Heap

Posted 13 November 2011 - 06:32 PM

Try using this to debug your program:

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

Was This Post Helpful? 0
  • +
  • -

#9 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

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.

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

Was This Post Helpful? 1
  • +
  • -

#10 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

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.
Was This Post Helpful? 0
  • +
  • -

#11 defiant91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 13-November 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! :)
Was This Post Helpful? 0
  • +
  • -

#12 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Re: Minimum Heap

Posted 13 November 2011 - 08:26 PM

No problem.
Was This Post Helpful? 0
  • +
  • -

#13 ishkabible  Icon User is offline

  • spelling expret
  • member icon





Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

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 :)

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

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1