Introduction to Heap

Definition of a heap

A heap is a data structure that contains objects which have comparable keys.

Uses of Heap
Some uses for a heap include: keeping track of employee records where the social security number is the key, network edges, events where there is a priority, etc.


Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes.

Heap ADT (Abstract Data Type)
There are two basic operations for a heap.

1. Insert - add a new object to the heap
   Running time - O (log n)
2. Extract-min - remove an object in the heap with a minimum key value (with ties broken arbitrarily). You could always makes this an extract-max operation or negate every key and you will get the maximum when you extract-min.
   Running time - O (log n)

Note that heap can either support extractMin or extractMax, if you want both operations supported simultaneously, then use Binary Search tree.

Other operations supported

• Heapify or BuildHeap - Initializes the heap in linear time i.e. O(n). Of-course you can use insert function, but then it will take O(log n) time per element, and so n log n time for n elements.
• Delete -  You can delete any element from the heap in O (log n) time.

The running time for both operations is O(logn) where n is the number of objects in the heap. Some additional operations heap supports Another operation is heapify, which inserts a batch of objects into the heap. This seems like it should run in O(nlogn) but it can actually be done in O(n) by inserting the values in batch. Deletion can also be done in O(logn) time.

Implementing a heap
Conceptually,heap is an almost complete binary tree where the data (key) stored in a node is larger than those of its children nodes (i.e. concept of comparability) .

So, to understand heap, we have to see 2 views of heap - tree and array.

Tree view of heap

Heap must satisfy following properties :

1. Heap is a binary tree - i.e. each node will have 0 or 1 or 2 children. 
2. Heap is almost complete tree - All nodes are filled in, except the last level may have some nodes missing toward the right. For eg. :
   

   

   Almost Complete Binary Tree

3. Heap Property - The key at any node is less than or equal to the keys of each of its children (if it has any). Because of this property, root of the minHeap is the smallest element.
   So, at every node x
   key[x] <= all keys of x's children
   (Also, Except root, all the nodes do have the parent.)
   Eg.
   
   
   
   Though, heap property puts some ordering of structure, but in no way guarantees the order for given keys
   

Array Implementation of Heap

Implementing the Operations of heap
Consider the operations one by one:

• Insertion
• MinHeap
• BuildHeap
• Delete

Cases when Implementing Binary heaps
Immutability of Keys

• Assumption - Clients don't change the keys. So, better is to make the key class immutable. Like in Java - String, Integer, Double, Color, Vector, Transaction, Point2D are immutable, but these are mutable - StringBuilder, Stack, Counter, Java array.

Thanks.
Source