Heap Implementation

Posted on | In , |

Priority Queue

  • It is an abstract data type such as stack or queue
  • But every item has an additional property: a priority value
  • Priority Queue is usually implemented with heaps, but it can be implemented with self balancing trees as well
  • The highest priority element is retrieved first, no FIFO structure here
  • Operation: InsertWithPriority(data, priority), getHighestPriorityElement(), peek()

Heap

  • It is basically a binary tree
  • Two main binary heap types: min and max heap
  • In a max heap, the keys of parent nodes are always greater than or equal to those of the children, the highest key is in the root node
  • It cannot be unbalanced! We insert every new item to the next available place
  • Application: Dijkstra algorithm, Prims algorithm

Heap Sort

  • Comparison-based algorithm
  • Use heap data structure rather than a linear-time search to find the maximum
  • Generally a little bit slower than quick sort, it has the advantage of a more favorable worst-case O(nlogn) runtime
  • Does NOT need additional memory
  • First we have to construct the heap itself from the numbers we want to sort -> O(n)
Operation Time Complexity
Find min/max O(1)
Remove min/max O(log(n))
Insert O(log(n))

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Heap(object):

    HEAP_SIZE = 10

    def __init__(self):
        self.heap = [0] * Heap.HEAP_SIZE
        self.currentPosition = -1

    def insert(self, item):

        if self.isFull():
            print('Heap is full...')
            return

        self.currentPosition = self.currentPosition + 1
        self.heap[self.currentPosition] = item
        self.fixUp(self.currentPosition)

    def fixUp(self, index):

        parentIndex = int((index - 1) / 2)

        while parentIndex >= 0 and self.heap[parentIndex] < self.heap[index]:
            temp = self.heap[index]
            self.heap[index] = self.heap[parentIndex]
            self.heap[parentIndex] = temp
            parentIndex = int((index - 1) / 2)

    def heapsort(self):

        for i in range(self.currentPosition + 1):
            temp = self.heap[0]
            print(temp)
            self.heap[0] = self.heap[self.currentPosition - i]
            self.heap[self.currentPosition] = temp
            self.fixDown(0, self.currentPosition - i - 1)

    def fixDown(self, index, upto):

        while index <= upto:

            leftChild = 2 * index + 1
            rightChild = 2 * index + 2

            if leftChild < upto:
                childToSwap = None

                if rightChild > upto:
                    childToSwap = leftChild
                else:
                    if self.heap[leftChild] > self.heap[rightChild]:
                        childToSwap = leftChild
                    else:
                        childToSwap = rightChild

                if self.heap[index] < self.heap[childToSwap]:
                    temp = self.heap[index]
                    self.heap[index] = self.heap[childToSwap]
                    self.heap[childToSwap] = temp
                else:
                    break

                index = childToSwap
            else:
                break

    def isFull(self):
        if self.currentPosition == heap.HEAP_SIZE:
            return True
        else:
            return False


if __name__ == '__main__':

    heap = Heap()
    heap.insert(10)
    heap.insert(-20)
    heap.insert(0)
    heap.insert(2)

    heap.heapsort()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# heap in Python
from heapq import heappop, heappush, heapify

heap = []
nums = [12, 3, -2, 6, 4, 8, 9]

# for num in nums:
#     heappush(heap, num)

# while heap:
#     print(heappop(heap))

heapify(nums)

print(nums) # >>> [-2, 3, 8, 6, 4, 12, 9]
0%