Heaps – Heap is a form of binary
tree. Its underlying data structure can be a list with children nodes in 2k+1
and 2k+2 position It could be a max-heap or min-heap.
A max-heap is kind of heap with top node (root
node) having the maximum value.
Heap (minheap) provide optimal time for all three –
insert, findminimum, deleteminimum.
The children index (2i and 2i + 1) can found
very easily as multiplying by 2 is nothing BUT LEFT SHIFT. Parent on the other
hand(i/2) can be found using RIGHT SHIFT.
Priority queues are implemented using heaps.
(min-heap).
MAX-HEAPIFY – This operation when done on a list A
in position i i.e MAX-HEAPIFY(A,i) brings the ith element “downwards” (if it is smaller), so the
subtree rooted at i obeys MAX HEAP PROPERTY.
Implementation of MAX-HEAPIFY in Python –
def max_heapify(A, i):
left = 2
* i + 1
right =
2 * i + 2
largest
= i
if left
< len(A) and A[left] > A[largest]:
largest = left
if right
< len(A) and A[right] > A[largest]:
largest = right
if
largest != i:
A[i], A[largest] = A[largest], A[i]
max_heapify(A, largest)
The complexity of MAX-HEAPIFY is O(logn).
To build
a MAX-HEAP, you run MAX-HEAPIFY on the lower nodes (having children)
UPTO to the top node. There is no point in running MAX-HEAPIFY on bottommost
children nodes.
So for array of size n, you run MAX-HEAPIFY from
floor(n/2) till the top node (i.e n=0). Below is the implementation –
def buildmaxheap(list):
i=int(len(list)/2)
while
(i>=0):
max_heapify(list,i)
i=i-1
The above is the fundamental step of heapsort.
Following steps are done in heapsort –
1)
Build max-heap (A)
2)
From last element to i=1, loop
3)
Exchange current element with A[0] //top most
element.
4)
Reduce heap-size, so that the last element is
disconnected.
5)
Run MAX-HEAPIFY(A,0)
Below is the implementation –
i = len(list)
list2 = []
while (i>0):
list[i-1],list[0] = list[0],list[i-1]
list2.append(list.pop())
max_heapify(list,0)
i = i-1
