Writing a Heap

[massivefermion]

Hi
I'm trying to write a heap data structure but I have no idea how to do this.Could Someone help?
thanks

[Salem]

> Could Someone help?
http://www.catb.org/~esr/faqs/smart-questions.html#prune

[massivefermion]

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?)

[mvmalderen]

>I tried to write a Heap in C++ but I couldn't
Can you at least post what you've tried then?

[massivefermion]

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.

[mvmalderen]

I want to know what exactly the "heap" you plan to write in C++ involves?

[Nick Evan]

.Just tell me how to write a heap data structure class in C++.

heap
Also look here
And a
lazy link

If you want descent information, ask a descent question.

[massivefermion]

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]

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]

And one more question.How should I pronounce the first name of C++'s inventor,Bjarne strostroup?

[mvmalderen]

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!!)