Data Structure and Algorithm

/****************************************
APPLICATION : Program to create a Heap
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE         : 2010 - October - 26
****************************************/

#include <iostream.h>
#include <conio.h>

struct Node //structure to represent a node of a tree
{
int data;
struct Node *left,*right;
};

typedef Node node;

node *New;
void create() //function to create and initialize a node
{
New = new node;
New -> left = NULL;
New -> right = NULL;
}

node *loc;
int n,*key;
void find(node *nd,int Item) //function to find the location of an item
{
if(nd != NULL)
  {
   if(nd -> data == Item)
    loc = nd; //save location
   find(nd -> left,Item);
   find(nd -> right,Item);
  }
}

void swap(int a,int b) //function to swap elements in an array (key)
{
int x = key[a];
int y = key[b];
key[a] = y;
key[b] = x;
}

void arrange() //function to arrange the input array using the property of heap
{
for(int i = 2;i <= n;i++)
  {
   int parent = int(i/2);
   int j = i;
   if(key[j] > key[parent])
   {
    while(parent >= 1)
    {
     if(key[j] > key[parent])
      swap(j,parent);
     j = parent;
     parent = parent/2;
    }
   }
  }
}

void makeHeap(node *&n,int Item,int parent) //function to build a heap from input array
{
if(n == NULL) //if first data
  {
   n = new node;
   n -> data = Item;
   n -> left = NULL;
   n -> right = NULL;
   return;
  }

create(); //create a node
New -> data = Item; //insert data
find(n,parent); //find location of parent of an item
node *p = loc;
if(p -> left == NULL) //if left of parent is empty
  p -> left = New;
else
  p -> right = New;
}

void display() //display the data of heap
{
for(int i = 1;i <= n;i++)
  cout << key[i] << ' ';
}

int main()
{
node *nd = NULL;
cout << "How many numbers? ";
cin >> n;
key = new int[n+1]; //allocate memory
cout << endl << "Enter " << n << " elements\n";
for(int i = 1;i <= n;i++)
  cin >> key[i];
arrange(); //arrange input array
for(int i = 1;i <= n;i++)
  {
   int parent = int(i/2);
   makeHeap(nd,key[i],key[parent]);
  }

cout << "\nHeap Created";
cout << "\n------------\n";
display();
getch();
return 0;
}

OUTPUT

How many numbers? 8

Enter 8 elements
44 30 50 22 60 55 77 55

Heap Created
77 55 60 50 30 44 55 22

DESCRIPTION

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) = key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.)

The binary heap data structures is an array that can be viewed as a complete binary tree. Each node of the binary tree corresponds to an element of the array. The array is completely filled on all levels except possibly lowest.

The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child can be computed

PARENT (i)
  return floor(i/2)
LEFT (i)
  return 2i
RIGHT (i)
  return 2i + 1

Let's try these out on a heap to make sure we believe they are correct. Take this heap,

which is represented by the array [20, 14, 17, 8, 6, 9, 4, 1].

We'll go from the 20 to the 6 first. The index of the 20 is 1. To find the index of the left child, we calculate 1 * 2 = 2. This takes us (correctly) to the 14. Now, we go right, so we calculate 2 * 2 + 1 = 5. This takes us (again, correctly) to the 6.

Now let's try going from the 4 to the 20. 4's index is 7. We want to go to the parent, so we calculate 7 / 2 = 3, which takes us to the 17. Now, to get 17's parent, we calculate 3 / 2 = 1, which takes us to the 20.

Download Original File