ProgrammingThis 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.
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 LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
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.
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.
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;
}
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.
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.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.