LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 11-20-2007, 03:13 AM   #1
ShaqDiesel
Member
 
Registered: Jul 2005
Posts: 144

Rep: Reputation: 15
Min Heap


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.
 
Old 11-20-2007, 06:56 AM   #2
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

Rep: Reputation: 108Reputation: 108
Does "calloc()" do what you are asking?
(see "man calloc")
 
Old 11-20-2007, 12:20 PM   #3
dmail
Member
 
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
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.

Last edited by dmail; 11-20-2007 at 12:22 PM.
 
Old 11-20-2007, 12:43 PM   #4
95se
Member
 
Registered: Apr 2002
Location: Windsor, ON, CA
Distribution: Ubuntu
Posts: 740

Rep: Reputation: 32
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;
}

Last edited by 95se; 11-20-2007 at 12:46 PM.
 
Old 11-20-2007, 06:30 PM   #5
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian
Posts: 2,543

Rep: Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880
Quote:
Originally Posted by ShaqDiesel View Post
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.
 
Old 03-26-2008, 06:30 PM   #6
ata2
LQ Newbie
 
Registered: Mar 2008
Posts: 1

Rep: Reputation: 0
Thumbs down Error in the array access to elements

Quote:
Originally Posted by 95se View Post
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
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to increase Heap Size? rajat Programming 1 08-01-2007 07:33 AM
Heap in nasm des_a Programming 2 06-25-2007 12:17 AM
3.8 Gb Suse 10.1 slow install in 1h30 min. Mandriva 2006 was less than 40 min Emmanuel_uk Linux - Distributions 2 06-15-2006 10:27 AM
heap or stack yashwantpinge Programming 1 03-17-2006 08:25 AM
increasing heap size podollb Linux - Software 3 03-07-2005 12:42 AM


All times are GMT -5. The time now is 03:23 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration