What is a Heap ?

A heap is a partially ordered complete binary tree. To say that a heap is partially ordered is to say that there is some relationship between the value of a node and the values of its children. In a min-heap, the value of a node is less than or equal to the values of its children. In a max-heap, the value of a node is greater than or equal to the values of its children. Consequently, the smallest (largest) value in a min-heap (max-heap) is at the heap's root. The heap ADT appears below.

An array A that presents a heap with two attributes:

  • length[A] : the number of elements in the array.
  • heap‐size[A] : the number of elements in the heap stored with  array A.
  • length[A] ≥ heap‐size[A]

The following is a heap representation in an Array.

 

If a complete binary tree with n nodes is represented  sequentially, then for any node with index i1 ≤i ≤n, we have

  • A[1] is the root of the tree
  • the parent PARENT(i) is at [ i / 2 ] if  i ≠1
  • the left child LEFT(i) is at 2i
  • the right child RIGHT(i) is at 2i+1

 

 

There are two kind of binary heaps: max‐heaps and min‐heaps.

MAX – Heap : In a max‐heap, the max‐heap property is that for every node i  other than the root

              A[PARENT(i) ]  ≥ A[i].

The largest element in a max‐heap is stored at the root. The subtree rooted at a node contains values no larger than that contained at the node itself.

 

MIN– Heap : In a min‐heap, the min‐heap properties that for every node i  other than the root, the smallest element in a min‐heap is at the root. The subtree rooted at a node contains values no smaller than that contained at the node itself.

            A[PARENT(i) ] ≤ A[i]

Following are the Example of MAX & MIN Heap

 

 

 

Algorithm 12 Heap 12

FOLLOW US ON LinkedIn



Explore Tutu'rself