Heap And Binary Heap

What is HEAP?

A heap is a tree with some special properties. The basic requirement of a heap is that the value of a node must be ≥ (or ≤) than the values of its children. This is called heap property.

Types of Heaps? 

Based on the property of a heap we can classify heaps into two types:

• Min heap: The value of a node must be less than or equal to the values of its children

• Max heap: The value of a node must be greater than or equal to the values of its children

Priority Queue ADT Through Heap - See Link

Algorithm for Inserting a data - we have arr[] and count in heap structure

• Count++
• i = count-1
• while(i>=0)
• findParent = (i-1)/2
• if Parent != -1 And  data < arr[parent]
• arr[i] = arr[parent]
• i = parent
• arr[i] = data

Algorithm to delete and Heapify

• Swap last most element with top element
• count --
• i=0
• heapify(i)
• find left child of  i
• find right child of i
• min = minimum of left/right/i
• if min != i
• Swap arr[i] and arr[min]
• heapify(min) -> recursive call