Heap is a data structure which is usually used to implement a priority queue, allowing us both enqueue and dequeue items in \(O(\log n) \).
Educative Approach
This can be easily implemented in python.
You can find it at Binary Heap Implementation
1 class BinHeap:
2 def __init__(self):
3 self.heapList = [0]
4 self.currentSize = 0
5
6 def percUp(self,i):
7 while i // 2 > 0:
8 if self.heapList[i] < self.heapList[i // 2]:
9 tmp = self.heapList[i // 2]
10 self.heapList[i // 2] = self.heapList[i]
11 self.heapList[i] = tmp
12 i = i // 2
13
14 def percDown(self,i):
15 while (i * 2) <= self.currentSize:
16 mc = self.minChild(i)
17 if self.heapList[i] > self.heapList[mc]:
18 tmp = self.heapList[i]
19 self.heapList[i] = self.heapList[mc]
20 self.heapList[mc] = tmp
21 i = mc
22
23 def minChild(self,i):
24 if i * 2 + 1 > self.currentSize:
25 return i * 2
26 else:
27 if self.heapList[i*2] < self.heapList[i*2+1]:
28 return i * 2
29 else:
30 return i * 2 + 1
31
32 def insert(self,k):
33 self.heapList.append(k)
34 self.currentSize = self.currentSize + 1
35 self.percUp(self.currentSize)
36
37 def delMin(self):
38 retval = self.heapList[1]
39 self.heapList[1] = self.heapList[self.currentSize]
40 self.currentSize = self.currentSize - 1
41 self.heapList.pop()
42 self.percDown(1)
43 return retval
44
45 def buildHeap(self,alist):
46 i = len(alist) // 2
47 self.currentSize = len(alist)
48 self.heapList = [0] + alist[:]
49 while (i > 0):
50 self.percDown(i)
51 i = i - 1Quick Approach
It is good to understand what happened above. But for quick application of min heap, python already provides a build-in module heapq. see here.
You can get start from:
heapq.heapify(x)create a heap from listxin place.xbecomes a min heap.heapq.heappush(heap, item)pushitemintoheap.heapq.heappop(heap, item)popitemout fromheap.