Heap

MaxHeap and MinHeap

Definition

 A MaxHeap is a complete binary tree where the value stored in any of its nodes is greater than or equal to the values stored in its child nodes.
A MinHeap is a complete binary tree where the value stored in any of its nodes is less than or equal to the values stored in its child nodes.

REPRESENTATION

 Being a complete binary tree, the most appropriate representation for a heap is the sequential representation. So it is enough to store in a vector the information associated with the nodes, the relationships between the nodes being described by the formulas:
- st(x)=2*x (if 2*x<=n) or NULL (if 2*x>n);
- dr(x)=2*x+1(if 2*x+1<=n) or NULL (if 2*x+1>n);
- tata(x)=[x/2] (if x>1) or NULL (if x=1 is the root);
- where x is a random node from the graph and n is the number of nodes in the tree

Introductory Notions

  1. Trees
  2. Binary trees
  3. Heaps

Min-Heap generator

Heap

  1. Creation
  2. Insert node
  3. Combination
  4. Extract node

Priority queue

Applications

Dictionary


Using the sequential representation, we can reformulate the definition of a heap as:

Definition

 The array H[1..n] is a MaxHeap if H[i]<=H[i/2], i=1,n;
The array H[1..n] is a MinHeap if H[i]>=H[i/2], i=1,n;