Heap is a specialized tree-based data structure that satisfies the heap property that 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.

—It is a binary tree with the following properties:

  • Property 1: it is a complete binary tree
  • Property 2: the value stored at a node is greater or equal to the  values stored at the children   (heap property)
—From Property 2, the largest value of the heap is always stored at the root.

Heap implementation using array representation

—A heap is a complete binary tree, so it is easy to be implemented using an array representation

Heap Specification

struct Heap {
  void ReheapDown(int, int);
  void ReheapUp(int, int);
  int *elements;
  int numElements;   // heap elements

The ReheapDown function (used by deleteItem)

void Heap::ReheapDown(int root, int bottom)
 int maxChild, rightChild, leftChild;

 leftChild = 2*root+1;
 rightChild = 2*root+2;

 if(leftChild <= bottom) // left child is part of the heap
   if(leftChild == bottom) // only one child
        maxChild = leftChild;
        if(elements[leftChild] <= elements[rightChild])
            maxChild = rightChild;
            maxChild = leftChild;
   if(elements[root] < elements[maxChild])
       Swap(elements, root, maxChild);
       ReheapDown(maxChild, bottom);

ReheapUp function

void Heap::ReheapUp(int root, int bottom)
 int parent;

 if(bottom > root) // tree is not empty
   parent = (bottom-1)/2;
   if(elements[parent] < elements[bottom])
     Swap(elements, parent, bottom);
     ReheapUp(root, parent);

Removing the largest element from the heap

(a) Copy the bottom rightmost element to the root

(b) Delete the bottom rightmost node
(c) Fix the heap property by calling ReheapDown

Inserting a new element into the heap

(a) Insert the new element in the next bottom leftmost place

(b) Fix the heap property by calling ReheapUp

Applications of Heap

  1. Priority Queues
  2. Heap-sort
  3. Graph algorithms
  4. Dijkstra’s shortest path algorithm
Tagged with: C/C++ languageData structures

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.