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

7 Years
Discussion Span
Last Post by mvmalderen

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


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.


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 <iomanip.h>

template <typename type> class Heap{
		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];
      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;

template <typename type> Heap<type>::Heap(int MAXSIZE){

	int *HeapArrayPtr = new int[MAXSIZE] ;
	MaxHeapSize = MAXSIZE;

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;
	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:

template <typename type> type Heap<type>::Delete(){

	int Temp;
	if (HeapSize == 0){
		cerr << "Cannot remove from an empty heap" << endl;
	Temp = HeapArrayPtr[0];   // Item at index 0 is the smallest
	HeapArrayPtr[0] = HeapArrayPtr[HeapSize - 1];// copy last one to root:
	FilterDown(0);   // readjust to be a heap
	return Temp;

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:

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:

template <typename type> void Heap<type>::Insert(type Item){

   if (HeapSize == MaxHeapSize){
      cerr << "Cannot insert into a full heap" << endl;
   HeapArrayPtr[HeapSize] = Item;// At first, place item at the end of the heap:
   FilterUp(HeapSize);   // restore heap property

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;


template <typename type> type Heap<type>::FindMin(){
	type Temp;
	if (HeapSize == 0){
		cerr << "empty heap" << endl;

	return  Temp = HeapArrayPtr[0];   // Item at index 0 is the smallest

template <typename type> type Heap<type>::FindMax(){

	type temp1;
	if (HeapSize == 0){
		cerr << "empty heap" << endl;

	for(int i=1; i<MaxHeapSize; i++){
    return temp1;

template <typename type> void Heap<type>::Remove(type item){

	for(int i=0; i<MaxHeapSize; i++){
		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);
	int max=h.FindMax();
	int min=h.FindMin();
	for(int i=1;i<=10;++i) cout<<h[i];
	int a[10],b=10;
	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?

Edited by Nick Evan: n/a


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!


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

Damn mate, you're lazy!!!!!
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.