Hi
I'm trying to write a heap data structure but I have no idea how to do this.Could Someone help?
thanks
massivefermion 3 Junior Poster
Salem 5,199 Posting Sage
massivefermion 3 Junior Poster
I tried to write a Heap in C++ but I couldn't so I googled about it but I found nothing useful so I came here to know that is there somebody who can help me to write a binary heap data structure that can implement both max and min heap in C++.
(Was it proper?)
tux4life 2,072 Postaholic
>I tried to write a Heap in C++ but I couldn't
Can you at least post what you've tried then?
massivefermion 3 Junior Poster
I simply wrote nothing.I just wanted to ask how to write a heap but you are confusing me and yourself with your posts.Just tell me how to write a heap data structure class in C++.I don't know what more do you want to know.
tux4life 2,072 Postaholic
I want to know what exactly the "heap" you plan to write in C++ involves?
massivefermion 3 Junior Poster
OK.I found a code one the internet with a lot of suffer(your lazy link was forbidden for me nick)And I changed it to be generic and overloaded [] operator for it,too.Here's the code:
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include <iomanip.h>
#include<time.h>
template <typename type> class Heap{
public:
Heap(int IntArray[], int Count);
Heap(int MAXSIZE);
type Delete();
void Insert(type Item);
type FindMax();
type FindMin();
bool IsEmpty(){ //IS EMPTY FUNCTION
return HeapSize == 0;
}
void SORT(type IntAarray[], int MAX);
void Remove(type item);
type operator[](int index){
return HeapArrayPtr[index];
}
private:
type * HeapArrayPtr; // pointer to array holding the heap data
int MaxHeapSize;
int HeapSize;
void FilterDown(int StartIndex);
void FilterUp(int StartIndex);
int Parent(int CurrentIndex){
return (CurrentIndex - 1) / 2;
}
int RightChild(int CurrentIndex){
return 2 * (CurrentIndex + 1);
}
int LeftChild(int CurrentIndex){
return 2 * CurrentIndex + 1;
}
};
//consrurctors
template <typename type> Heap<type>::Heap(int MAXSIZE){
int *HeapArrayPtr = new int[MAXSIZE] ;
MaxHeapSize = MAXSIZE;
HeapSize=0;
}
template <typename type> Heap<type>::Heap(int IntArray[], int Count){
int CurrentPosition;
if (Count <= 0){
cerr << "Cannot construct a heap with size 0 or less." << endl;
exit(1);
}
MaxHeapSize = Count;
HeapSize = Count;
HeapArrayPtr = IntArray;// a pointer assignment statement
CurrentPosition = (HeapSize - 2) / 2;// Set CurrentPosition to the last index of a parent node:
while (CurrentPosition >= 0){// Get heap condition for subtree rooted at index CurrentPosition:
FilterDown(CurrentPosition);
CurrentPosition--;
}
}
//DELETE()
template <typename type> type Heap<type>::Delete(){
int Temp;
if (HeapSize == 0){
cerr << "Cannot remove from an empty heap" << endl;
exit(1);
}
Temp = HeapArrayPtr[0]; // Item at index 0 is the smallest
HeapArrayPtr[0] = HeapArrayPtr[HeapSize - 1];// copy last one to root:
HeapSize--;
FilterDown(0); // readjust to be a heap
return Temp;
}
//FILTER DOWN()
template <typename type> void Heap<type>::FilterDown(int StartIndex){
int CurrentPosition, ChildPosition, RightChildPosition, Target;
CurrentPosition = StartIndex;
Target = HeapArrayPtr[StartIndex];
ChildPosition = LeftChild(CurrentPosition);
while (ChildPosition < HeapSize){
RightChildPosition = ChildPosition + 1;// Set ChildPosition to index of smaller of right, left children:
if ((RightChildPosition < HeapSize) && (HeapArrayPtr[RightChildPosition] <= HeapArrayPtr[ChildPosition]))
ChildPosition = RightChildPosition;
if (Target <= HeapArrayPtr[ChildPosition])
break; // Get out of loop, heap OK with Target at CurrentPosition
HeapArrayPtr[CurrentPosition] = HeapArrayPtr[ChildPosition];// Move value of the smaller child to the parent node:
CurrentPosition = ChildPosition;// Move down the tree:
ChildPosition = LeftChild(CurrentPosition);
}
HeapArrayPtr[CurrentPosition] = Target;// Put Target into the correct location:
}
//FILTER UP()
template <typename type> void Heap<type>::FilterUp(int StartIndex){
int CurrentPosition, ParentPosition;
type Target;
CurrentPosition = StartIndex;
ParentPosition = Parent(CurrentPosition);
Target = HeapArrayPtr[StartIndex];
while (CurrentPosition != 0){
if (HeapArrayPtr[ParentPosition] <= Target)
break; // Get out of loop, heap OK with Target at CurrentPosition
HeapArrayPtr[CurrentPosition] = HeapArrayPtr[ParentPosition];// Move parent value to child:
CurrentPosition = ParentPosition;// Move up in the tree:
ParentPosition = Parent(CurrentPosition);
}
HeapArrayPtr[CurrentPosition] = Target;// Place Target at the position located for it:
}
//INSERT()
template <typename type> void Heap<type>::Insert(type Item){
if (HeapSize == MaxHeapSize){
cerr << "Cannot insert into a full heap" << endl;
exit(1);
}
HeapArrayPtr[HeapSize] = Item;// At first, place item at the end of the heap:
FilterUp(HeapSize); // restore heap property
HeapSize++;
}
//SORT()
template <typename type> void Heap<type>::SORT(type IntArray[], int MAX){
type Smallest;
int a;
Heap (IntArray, MAX); // constructor makes IntArray a heap
for (a = MAX - 1; a >= 1; a--){
Smallest = Delete();// Remove smallest item and place at index k
IntArray[a] = Smallest;// At this point IntArray[0] contains the largest item by default
}
cout<<"print data in descending order"<<endl;
for (int k = 0; k <MAX; k++){
cout << setw(10) << IntArray[k];
}
cout << endl;
}
//FindMin()
template <typename type> type Heap<type>::FindMin(){
type Temp;
if (HeapSize == 0){
cerr << "empty heap" << endl;
exit(1);
}
return Temp = HeapArrayPtr[0]; // Item at index 0 is the smallest
}
//FINDMax()
template <typename type> type Heap<type>::FindMax(){
type temp1;
temp1=HeapArrayPtr[0];
if (HeapSize == 0){
cerr << "empty heap" << endl;
exit(1);
}
for(int i=1; i<MaxHeapSize; i++){
if(temp1<HeapArrayPtr[i])
temp1=HeapArrayPtr[i];
}
return temp1;
}
//Remove()
template <typename type> void Heap<type>::Remove(type item){
for(int i=0; i<MaxHeapSize; i++){
if(HeapArrayPtr[i]==item){
HeapArrayPtr[i] = HeapArrayPtr[HeapSize - 1];
// HeapSize--;
}
}
Heap(HeapArrayPtr, MaxHeapSize-1);
}With the main file like below:
#include "heap.h"
int main(){
Heap<int> h(10);
for(int i=1;i<=10;++i) h.Insert(i);
cout<<h.IsEmpty();
int max=h.FindMax();
int min=h.FindMin();
for(int i=1;i<=10;++i) cout<<h[i];
h.Remove(20);
int a[10],b=10;
h.SORT(a,b);
h.Delete();
Heap<int> g(a,b);
return 0;
}I get the don't send message when I execute the resulting exe file.
And I made the for-loop line a comment and there was no problem.But I couldn't find what is wrong with it.
Could you tell what is the problem?
massivefermion 3 Junior Poster
Hey I think with that big code,the question can't be seen but please pay attention there is a question in the post above!
massivefermion 3 Junior Poster
And one more question.How should I pronounce the first name of C++'s inventor,Bjarne strostroup?
tux4life commented: Damn mate, you're lazy!!!!! -3
tux4life 2,072 Postaholic
And one more question.How should I pronounce the first name of C++'s inventor,Bjarne strostroup?
Damn mate, you're (becoming) annoying, and you're lazy too. STFW!!!
http://en.wikipedia.org/wiki/Bjarne_Stroustrup
(Look at the phonetics, first sentence)
Or just look here: http://www.research.att.com/~bs/pronounciation.wav
(it is even at his own homepage!!)
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.