Not Yet Answered # Writing a Heap

Discussion Starter pywriter 3 mvmalderen 2,072 Discussion Starter pywriter 3 Discussion Starter pywriter 3 Discussion Starter pywriter 3 Discussion Starter pywriter 3 mvmalderen 2,072 Write a C program that should create a 10 element array of random integers (0 to 9). The program should total all of the numbers in the odd positions of the array and compare them with the total of the numbers in the even positions of the array and indicate ...

0

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

0

**>I tried to write a Heap in C++ but I couldn't**

Can you at least post what you've tried then?

0

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.

0

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?

*Edited 5 Years Ago by Nick Evan*: n/a

0

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!

-1

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

0

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

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hi. so this is actually a continuation from another question of mineHere but i was advised to start a new thread as the original question was already answered.

This is the result of previous question answered :

code for the listbox - datagridview interaction

At the top of the code ...

the function that I created to find the ...