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 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 


11202007, 02:13 AM

#1

Member
Registered: Jul 2005
Posts: 144
Rep:

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.



11202007, 05:56 AM

#2

Senior Member
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530
Rep:

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



11202007, 11:20 AM

#3

Member
Registered: Oct 2005
Posts: 970
Rep:

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; 11202007 at 11:22 AM.



11202007, 11:43 AM

#4

Member
Registered: Apr 2002
Location: Windsor, ON, CA
Distribution: Ubuntu
Posts: 740
Rep:

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; 11202007 at 11:46 AM.



11202007, 05:30 PM

#5

Senior Member
Registered: Nov 2005
Distribution: Debian
Posts: 2,456

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.



03262008, 05:30 PM

#6

LQ Newbie
Registered: Mar 2008
Posts: 1
Rep:

Error in the array access to elements
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



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 10:14 PM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

