Binary heap. Array-based internal representation.
Heap is a binary tree and therefore can be stored inside the computer using links. It gives various benefits; one of them is the ability to vary number of elements in a heap quite easily. On the other hand, each node stores two auxiliary links, which implies an additional memory costs. As mentioned above, a heap is a complete binary tree, which leads to the idea of storing it using an array. By utilizing array-based representation, we can reduce memory costs while tree navigation remains quite simple
As for the heapsort algorithm, array-based implementation is kind of native.
Mapping heap to array
A heap is stored in array level by level. The topmost level contains root only. It is mapped to the first element of an array (with index 0). Root's children are mapped to the second and third elements and so on. A heap is a complete binary tree, which guarantees, that heap's nodes take up places in the array compactly, making the mapping quite efficient.
///////////FILE 1 ////////////////
#ifndef BINARYHEAP_H
#define BINARYHEAP_H
class BinaryHeap
{
int * data;
int heapSize;
int arrayMaxSize;
public:
BinaryHeap(int size)
{
data = new int[size];
arrayMaxSize=size;
heapSize =0;
}
BinaryHeap(int size,int *array)
{
data = array;
arrayMaxSize=size;
heapSize =size;
}
virtual ~BinaryHeap()
{
delete[] data;
}
void heapify(int *arr,int index);
int getLeftChild(int index);
int getRightChild(int index);
int getParent(int index);
void printHeap();
void buildHeap();
protected:
private:
};
#endif // BINARYHEAP_H
////////////////FILE 2////////////
#include "binaryheap.h"
#include<iostream>
using namespace std;
void BinaryHeap::heapify(int *arr,int index)
{
if(index>heapSize || index> arrayMaxSize)
{
cout<<"The index you have provide is incorrect"<<endl;
return;
}
int maxindex = index;
int left= getLeftChild(index);
int right = getRightChild(index);
if(left<heapSize && arr[left]>arr[index])
{
maxindex = left;
}
if(right<heapSize && arr[right]>arr[maxindex])
{
maxindex=right;
}
if(index != maxindex)
{
int temp = arr[index];
arr[index] = arr[maxindex];
arr[maxindex] = temp;
heapify(arr,maxindex);
}
return;
}
int BinaryHeap::getLeftChild(int index)
{
return (2*index+1);
}
int BinaryHeap::getRightChild(int index)
{
return (2*index+2);
}
int BinaryHeap::getParent(int index)
{
return int((index-1)/2);
}
void BinaryHeap::buildHeap()
{
if(heapSize<=0)
{
return;
}
for(int i=(heapSize-2)/2;i>=0;i--)
{
cout<<" :"<<i;
heapify(data,i);
}
}
void BinaryHeap::printHeap()
{
int i=0;
cout<<" "<<endl;
while(i<heapSize)
{
cout<<*(data+i)<<", ";
i++;
}
cout<<" "<<endl;
}
//////////FILE 3 DRIVER - MAIN/////////////////
#include<iostream>
#include "binaryheap.h"
using namespace std;
#define SIZE 5
int main()
{
int *array = new int[SIZE];
int i =0;
cout<<" enter the data"<<endl;
while(i<SIZE)
{
cin>>array[i];
i++;
}
i=0;
/* while(i<10)
{
cout<<" "<<array[i];
i++;
}*/
BinaryHeap* heap = new BinaryHeap(SIZE,array);
heap->printHeap();
heap->buildHeap();
heap->printHeap();
return 1;
}
No comments:
Post a Comment