Min Heap

ShaqDiesel · 11-20-2007, 02:13 AM

I'm trying to find an example of building a min or max heap from a stream of data, like an array. All I've been able to find is how to build a heap from a complete binary tree. If someone could show me an example of how using an array, I can construct a min heap that would be greatly apprectiated. Thanks.

Hko · 11-20-2007, 05:56 AM

Does "calloc()" do what you are asking?
(see "man calloc")

dmail · 11-20-2007, 11:20 AM

Which language are you using ? C++ has in functions in the STL for creating heaps also a pqueue uses a heap struture. Creating a heap manually is a very simple operation once you understand the structure and algo itself.

edit/
I take it you mean the heap stucture rather than a memory heap? Hko's comment just confuses me.

95se · 11-20-2007, 11:43 AM

Hko: No, he's talking about a particular data structure. Here is an implementation of a max heap I wrote a while ago. You can add points/elements one at a time, so it would be suitable for a streaming implementation.

MaxHeap.h

Code:

#include <vector>
#include <exception>
#include <stdexcept>

using namespace std;

template <class Type>
class MaxHeap
{
private:
	vector<Type> * heap;
	

public:
	
	MaxHeap();
	~MaxHeap();
	
	void add(Type val);
	Type peek();
	Type pop();
	int size() { return heap->size(); }
	
private:
	int parent(int pos);
	int left(int pos);
	int right(int pos);
	void swap(int pos1, int pos2);
};

class heap_empty : public out_of_range
{
public:
	heap_empty(const string &message) : out_of_range(message) {;}
};

template <class Type> 
MaxHeap<Type>::MaxHeap()
{
	heap = new vector<Type>();
}

template <class Type>
MaxHeap<Type>::~MaxHeap()
{
	delete heap;
}

template <class Type>
void MaxHeap<Type>::add(Type val)
{
	int pos, parentPos;
	heap->push_back(val);
	pos = heap->size() - 1;

	/* perculate up */
	while(pos > 0) {
		parentPos = parent(pos);
		if((*heap)[pos] > (*heap)[parentPos]) {
			swap(pos, parentPos);
			pos = parentPos;
		} else {
			break;
		}
	}
}

template <class Type>
Type MaxHeap<Type>::pop()
{
	Type ret;
	int pos, l, r;
	
	if(heap->empty()) {
		throw new heap_empty("Can't get max when heap is empty!");
	}
	
	ret = (*heap)[0];
	
	(*heap)[0] = heap->back();
	heap->pop_back();
	pos = 0;
	l = left(pos);
	r = right(pos);
	
	/* perculate down */
	while(l < heap->size()) {
		if(r >= heap->size()) {
			if((*heap)[pos] < (*heap)[l]) {
				swap(pos, l);
			}
			break;
		}
		
		if(((*heap)[pos] > (*heap)[l]) && ((*heap)[pos] > (*heap)[r])) {
			break;
		}
		
		int swapPos = (((*heap)[l] > (*heap)[r]) ? l : r);
		swap(pos, swapPos);
		pos = swapPos;
		
		l = left(pos);
		r = right(pos);
	}
	
	return ret;
}

template <class Type>
Type MaxHeap<Type>::peek()
{
	if(heap->empty()) {
		throw new heap_empty("Can't peak when the heap is empty!");
	} else {
		return (*heap)[0];
	}
}

template <class Type>
int MaxHeap<Type>::parent(int pos)
{
	if(pos <= 0) {
		throw new out_of_range("Can't find the parent of an element < 0.");
	}
	
	return (pos - 1) >> 1;
}

template <class Type>
int MaxHeap<Type>::left(int pos)
{
	return (pos << 2) + 1;
}

template <class Type>
int MaxHeap<Type>::right(int pos)
{
	return (pos << 2) + 2;
}

template <class Type>
void MaxHeap<Type>::swap(int pos1, int pos2)
{
	if(!heap->empty() && (pos1 < 0 || pos1 >= heap->size()) && (pos2 < 0 || pos2 >= heap->size())) {
		throw new out_of_range("It seems pos1 or pos2 is out of bounds.");
	}
	
	Type temp = (*heap)[pos1];
	(*heap)[pos1] = (*heap)[pos2];
	(*heap)[pos2] = temp;
}

ntubski · 11-20-2007, 05:30 PM

Quote:

Originally Posted by ShaqDiesel

I'm trying to find an example of building a min or max heap from a stream of data, like an array. All I've been able to find is how to build a heap from a complete binary tree. If someone could show me an example of how using an array, I can construct a min heap that would be greatly apprectiated. Thanks.

The way I was taught, heaps are always built from an array, but the programmer looks at the array as if it was a binary tree: a[1] is the root, a[2*i] is the left child of a[i], a[2*i + 1] is the right child. I guess you could use an actual tree instead.

The wikipedia article on heapsort has an algorithm for building a heap from an array: http://en.wikipedia.org/wiki/Heap_sort see the heapify function.

ata2 · 03-26-2008, 05:30 PM

Quote:

Originally Posted by 95se

Hko:
No, he's talking about a particular data structure. Here is an implementation of a max heap I wrote a while ago. You can add points/elements one at a time, so it would be suitable for a streaming implementation.

MaxHeap.h

Code:

int MaxHeap<Type>::parent(int pos)
{
	if(pos <= 0) {
		throw new out_of_range("Can't find the parent of an element < 0.");
	}
	
	return (pos - 1) >> 1;
}

template <class Type>
int MaxHeap<Type>::left(int pos)
{
	return (pos << 2) + 1;
}

template <class Type>
int MaxHeap<Type>::right(int pos)
{
	return (pos << 2) + 2;
}
pos2] = temp;
}

Except that your code is actually buggy

If the heap is stored in an array with indexes [0..2^n]
then the access functions are defined by the following macros:

#define PARENT(pos) (pos>>1) // equivalent to floor(pos/2)
#define LEFT(pos) ((pos<<1)+1) // equivalent to pos*2 + 1
#define RIGHT(pos) ((pos<<1)+2) // equivalent to pos*2 + 2

According to your scheme the children of node 1 (which are stored in offset 3 and 4) can be found in:

left => (1*4)+1 = 5
right => (1*4)+2 = 6

Which is clearly incorrect...
Remember that A << B multiplies A by 2 B times.

Cheers, Andrea