classBinaryHeap {constructor () {this.heap = [] }insert (value) {this.heap.push(value)this.heapify() }size () {returnthis.heap.length }empty () {returnthis.size() ===0 }// using iterative approach to reorder the heap after insertionheapify () {let index =this.size() -1while (index >0) {constelement=this.heap[index]constparentIndex=Math.floor((index -1) /2)constparent=this.heap[parentIndex]if (parent[0] >= element[0]) breakthis.heap[index] = parentthis.heap[parentIndex] = element index = parentIndex } }// Extracting the maximum element from the HeapextractMax () {constmax=this.heap[0]consttmp=this.heap.pop()if (!this.empty()) {this.heap[0] = tmpthis.sinkDown(0) }return max }// To restore the balance of the heap after extraction.sinkDown (index) {constleft=2* index +1constright=2* index +2let largest = indexconstlength=this.size()if (left < length &&this.heap[left][0] >this.heap[largest][0]) { largest = left }if (right < length &&this.heap[right][0] >this.heap[largest][0]) { largest = right }// swapif (largest !== index) {consttmp=this.heap[largest]this.heap[largest] =this.heap[index]this.heap[index] = tmpthis.sinkDown(largest) } }}constmaxHeap=newBinaryHeap()maxHeap.insert([4])maxHeap.insert([3])maxHeap.insert([6])maxHeap.insert([1])maxHeap.insert([8])maxHeap.insert([2])while (!maxHeap.empty()) {constmx=maxHeap.extractMax()console.log(mx)}
/* Minimum Priority Queue* It is a part of heap data structure* A heap is a specific tree based data structure* in which all the nodes of tree are in a specific order.* that is the children are arranged in some* respect of their parents, can either be greater* or less than the parent. This makes it a min priority queue* or max priority queue.*/// Functions: insert, delete, peek, isEmpty, print, heapSort, sinkclassMinPriorityQueue {// calls the constructor and initializes the capacityconstructor (c) {this.heap = []this.capacity = cthis.size =0 }// inserts the key at the end and rearranges it// so that the binary heap is in appropriate orderinsert (key) {if (this.isFull()) returnthis.heap[this.size +1] = keylet k =this.size +1while (k >1) {if (this.heap[k] <this.heap[Math.floor(k /2)]) {consttemp=this.heap[k]this.heap[k] =this.heap[Math.floor(k /2)]this.heap[Math.floor(k /2)] = temp } k =Math.floor(k /2) }this.size++ }// returns the highest priority valuepeek () {returnthis.heap[1] }// returns boolean value whether the heap is empty or notisEmpty () {returnthis.size ===0 }// returns boolean value whether the heap is full or notisFull () {if (this.size ===this.capacity) returntruereturnfalse }// prints the heapprint () {console.log(this.heap.slice(1)) }// heap sorting can be done by performing// delete function to the number of times of the size of the heap// it returns reverse sort because it is a min priority queueheapSort () {for (let i =1; i <this.capacity; i++) {this.delete() } }// this function reorders the heap after every delete functionsink () {let k =1while (2* k <=this.size ||2* k +1<=this.size) {let minIndexif (this.heap[2* k] >=this.heap[k]) {if (2* k +1<=this.size &&this.heap[2* k +1] >=this.heap[k]) {break } elseif (2* k +1>this.size) {break } }if (2* k +1>this.size) { minIndex =this.heap[2* k] <this.heap[k] ?2* k : k } else {if (this.heap[k] >this.heap[2* k] ||this.heap[k] >this.heap[2* k +1] ) { minIndex =this.heap[2* k] <this.heap[2* k +1] ?2* k :2* k +1 } else { minIndex = k } }consttemp=this.heap[k]this.heap[k] =this.heap[minIndex]this.heap[minIndex] = temp k = minIndex } }// deletes the highest priority value from the heapdelete () {constmin=this.heap[1]this.heap[1] =this.heap[this.size]this.heap[this.size] = minthis.size--this.sink()return min }}// testingconstq=newMinPriorityQueue(8)q.insert(5)q.insert(2)q.insert(4)q.insert(1)q.insert(7)q.insert(6)q.insert(3)q.insert(8)q.print() // [ 1, 2, 3, 5, 7, 6, 4, 8 ]q.heapSort()q.print() // [ 8, 7, 6, 5, 4, 3, 2, 1 ]
Overview of heap
2. Representation
In a min heap, when you look at the parent node and its child nodes, the parent node always has the smallest value. When a heap has an opposite definition, we call it a max heap. For the following discussions, we call a min heap a heap.
You can access a parent node or a child nodes in the array with indices below.
A root node|_i_ = 1, the first item of the array
A parent node|parent(i) = i / 2
A left child node|left(i) = 2_i_
A right child node|right(i)=2_i_+1
The parent node corresponds to the item of index 2 by parent(i) = 4 / 2 = 2. The child nodes correspond to the items of index 8 and 9 by left(i) = 2 * 2 = 4, right(i) = 2 * 2 + 1 = 5, respectively.
3. The way how to build a heap
You need two operations to build a heap from an arbitrary array.
min_heapify|make some node and its descendant nodes meet the heap property.
build_min_heap|produce a heap from an arbitrary array.
We can build a heap by applying min_heapify to each node repeatedly.
3.1 min_heapify
In min_heapify, we exchange some nodes with its child nodes to satisfy the heap property under these two features below;
Some node and its child nodes don’t satisfy the heap property,
That child nodes and its descendant nodes satisfy the property.
Here we define min_heapify(array, index). This method takes two arguments, array, and index. We assume this method exchange the node of array[index] with its child nodes to satisfy the heap property.
Now, this subtree satisfies the heap property by exchanging the node of index 4 with the node of index 8.
These operations above produce the heap from the unordered tree (the array).
3.2 build_min_heap
The pseudo-code below stands for how build_min_heap works.
build_min_heap(array)
for i=n/2 downto 1
do min_heapify(array, i)
Each node can satisfy the heap property with meeting the conditions to be able to apply min_heapfiy. This is because this function iterates the nodes from the bottom (the second last level) to the top (the root node level). For instance, this function first applies min_heapify to the nodes both of index 4 and index 5 and then applying min_heapify to the node of index 2. So the node of the index and its descendent nodes satisfy the heap property when applying min_heapify.
4. Time complexity
Let’s think about the time complexity of build_min_heap. First of all, we think the time complexity of min_heapify, which is a main part of build_min_heap.
min_heapify repeats the operation of exchanging the items in an array, which runs in constant time. So the time complexity of min_heapify will be in proportional to the number of repeating. In the worst case, min_heapify should repeat the operation the height of the tree times. This is because in the worst case, min_heapify will exchange the root nodes with the most depth leaf node. Assuming h as the height of the root node, the time complexity of min_heapify will take O(h) time.
So we should know the height of the tree to get the time complexity.
Finally, we get O(n) as the time complexity of build_min_heap. Also, we get O(log_n_) as the time complexity of min_heapify.
5. Implementation
Here we implement min_heapify and build_min_heap with Python. the implementation of min_heapify will be as follow.
defmin_heapify(array,i): left =2* i +1 right =2* i +2 length =len(array)-1 smallest = i if left <= length and array[i]> array[left]: smallest = leftif right <= length and array[smallest]> array[right]: smallest = rightif smallest != i: array[i], array[smallest]= array[smallest], array[i]min_heapify(array, smallest)
First, this method computes the node of the smallest value among the node of index i and its child nodes and then exchange the node of the smallest value with the node of index i. When the exchange happens, this method applies min_heapify to the node exchanged.
Index of a list (an array) in Python starts from 0, the way to access the nodes will change as follow.
The root node|_i_ = 0
The parent node|parent(i) = (i-1) / 2
The left child node|left(i) = 2_i_ + 1
The right child node|right(i)=2_i_+2
The variable, smallest has the index of the node of the smallest value. If the smallest doesn’t equal to the i, which means this subtree doesn’t satisfy the heap property, this method exchanges the nodes and executes min_heapify to the node of the smallest.
The implementation of build_min_heap is almost the same as the pseudo-code.
defbuild_min_heap(array):for i inreversed(range(len(array)//2)):min_heapify(array, i)
The for-loop differs from the pseudo-code, but the behavior is the same. This for-loop also iterates the nodes from the second last level of nodes to the root nodes.
6. Heapsort
Heapsort is one sort algorithm with a heap. It’s really easy to implement it with min_heapify and build_min_heap. The flow of sort will be as follow. Please note that the order of sort is ascending.
Build a heap from an arbitrary array with build_min_heap.
Swap the first item with the last item in the array.
Remove the last item from the array.
Run min_heapify to the first item.
Back to step 2.
In a heap, the smallest item is the first item of an array. The array after step 3 satisfies the conditions to apply min_heapify because we remove the last item after we swap the first item with the last item. By this nature, we can sort an array by repeating steps 2 to 4.
The implementation of heapsort will become as follow.
The time complexity of heapsort is O(n_log_n) because in the worst case, we should repeat min_heapify the number of items in array times, which is n.
In the heapq module of Python, it has already implemented some operation for a heap. I followed the method in MIT’s lecture, the implementation differs from Python’s. If you’d like to know Python’s detail implementation, please visit the source code here. For example, these methods are implemented in Python.
heapq.heapify | corresponds to build_min_heap
heapq.heapop | corresponds to swapping items, remove the last item, and min_heapify at once_._
"""Heaps (priority queues)"""# the maximum number of items that can be stored in the heapCAPACITY =10"""*** Max Heap ***----------------"""# define the heap classclassHeap(object):def__init__(self):# create array with as many slots as the CAPACITY self.heap = [0] * CAPACITY# track the size of the heap (the number of items in the heap) self.heap_size =0# insertion takes O(1) running time BUT we have to make sure that hte# heap properties are not violated (it takes O(logN) because of the# fixUp() method)definsert(self,item):# if the heap is at CAPACITY already we can not insert any more itemsif CAPACITY == self.heap_size:return# insert the item at the index of the size of the heap (the last# empty spot) and then increment the counter self.heap[self.heap_size]= item self.heap_size +=1# after insert check to see if the heap properties were violated and# if so fix them self.fix_up(self.heap_size -1)# we consider the last item and check whether swaps are needed or not# running time O(logN)deffix_up(self,index):# get the parent index of the given node in the heap parent_index = (index -1) //2# while the index > 0 means until we consider all the items "above"# the one we inserted we have to swap the node with the parent if the# heap property is violated# this is a MAX HEAP: largest items are in the higher layers (max# item == root node)if index >0and self.heap[index]> self.heap[parent_index]: self.swap(index, parent_index)# run the check again after the swap on the parent self.fix_up(parent_index)# Get max, return the root node. Because this is a max heap the root is# the max item. Because this is an array it takes O(1) time# this is the peek() methoddefget_max(self):return self.heap[0]# Get poll, returns the max item and also REMOVES the item from the heap# note: we just dont care about that item anymore but because we have an# array with fixed size we aren't able to get rid of it completely# O(logN) running timedefpoll(self):max= self.get_max()# first swap the first item with the last item self.swap(0, self.heap_size -1)# then decrement the heap size ( excludes the last item from the heap# going forward thus 'removing it') self.heap_size = self.heap_size -1# nex check if the heap properties have been violated and if so fix# them ( fix down is similar to fix up but works from the root down ) self.fix_down(0)# finally return the max item removedreturnmax# fix down, we have a given item in the heap and we consider all the# items below and check whether the heap properties are violated or notdeffix_down(self,index):# every node has 2 children so in the array the node i has left child# with index *i+1 and right child with index 2*i+2 index_left =2* index +1 index_right =2* index +2# this is a max heap so the parent is always greater than the children index_largest = index# if the left child is greater than the parent: largest is the left nodeif index_left < self.heap_size and self.heap[index_left]> self.heap[ index]: index_largest = index_left# figure out if the left child or right child is the greater one# first check if the given index is valid ( not larger than the heap# size)# if the right child is greater than the left child: largest is the# right nodeif index_right < self.heap_size and self.heap[index_right]>\ self.heap[index_largest]: index_largest = index_right# we don't want to swap items with themselvesif index != index_largest: self.swap(index, index_largest)# recursively check down the tree for any other heap violations# and fix them as needed self.fix_down(index_largest)# we have N items and we want to sort them with a heap# every poll operation takes O(logN) time because of the fix down# method thats why the overall running time is O(NlogN) for heapsortdefheap_sort(self):# we decrease the size of hte heap in the poll method so we have to# store it size = self.heap_sizefor i inrange(0, size):max= self.poll()print(max)# swap two items with (index1, index2) in the heap arraydefswap(self,index1,index2): self.heap[index2], self.heap[index1]= self.heap[index1], self.heap[index2]heap =Heap()heap.insert(10)heap.insert(8)heap.insert(12)heap.insert(20)heap.insert(-2)heap.insert(0)heap.insert(1)heap.insert(321)heap.heap_sort()
# Implements a min-heap. For max-heap, simply reverse all comparison orders.## Note on alternate subroutine namings (used in some textbooks):# - _bubble_up = siftdown# - _bubble_down = siftupdef_bubble_up(heap,i):while i >0: parent_i = (i -1) //2if heap[i]< heap[parent_i]: heap[i], heap[parent_i]= heap[parent_i], heap[i] i = parent_icontinuebreakdef_bubble_down(heap,i): startpos = i newitem = heap[i] left_i =2* i +1while left_i <len(heap):# Pick the smaller of the L and R children right_i = left_i +1if right_i <len(heap)andnot heap[left_i]< heap[right_i]: child_i = right_ielse: child_i = left_i# Break if heap invariant satisfiedif heap[i]< heap[child_i]:break# Move the smaller child up. heap[i], heap[child_i]= heap[child_i], heap[i] i = child_i left_i =2* i +1defheapify(lst):for i inreversed(range(len(lst) //2)):_bubble_down(lst, i)defheappush(heap,item): heap.append(item)_bubble_up(heap, len(heap) -1)defheappop(heap):iflen(heap)==1:return heap.pop() min_value = heap[0] heap[0]= heap[-1]del heap[-1]_bubble_down(heap, 0)return min_value# Example usageheap = [3,2,1,0]heapify(heap)print('Heap(0, 1, 2, 3):', heap)heappush(heap, 4)heappush(heap, 7)heappush(heap, 6)heappush(heap, 5)print('Heap(0, 1, 2, 3, 4, 5, 6, 7):', heap)sorted_list = [heappop(heap)for _ inrange(8)]print('Heap-sorted list:', sorted_list)# Large test case, for randomized testsimport random# Heapify 0 ~ 99heap =list(range(100))random.shuffle(heap)heapify(heap)# Push 100 ~ 199 in random ordernew_elems =list(range(100, 200))random.shuffle(new_elems)for elem in new_elems:heappush(heap, elem)sorted_list = [heappop(heap)for _ inrange(200)]print(sorted_list ==sorted(sorted_list))
A heap is one common implementation of a priority queue. A priority queue contains items with some priority. You can always take an item out in the priority order from a priority queue. It is important to take an item out based on the priority. When you look around poster presentations at an academic conference, it is very possible you have set in order to pick some presentations. Or you will make a priority list before you go sight-seeing (In this case, an item will be a tourist spot.). A stack and a queue also contain items. You can take an item out from a stack if the item is the last one added to the stack. This is first in, last out (FILO). As for a queue, you can take an item out from the queue if this item is the first one added to the queue. This is first in, first out (FIFO). You can regard these as a specific type of a priority queue. This is because the priority of an inserted item in stack increases and the priority of an inserted item in a queue decreases.
A heap is one of the tree structures and represented as a binary tree. I put the image of heap below. You can implement a tree structure by a pointer or an array. In this post, I choose to use the array implementation like below. In terms of space complexity, the array implementation has more benefits than the pointer implementation. The indices of the array correspond to the node number in the below image.
The heap above is called a min heap, and each value of nodes is less than or equal to the value of child nodes. We call this condition the heap property.
When you look at the node of index 4, the relation of nodes in the tree corresponds to the indices of the array below.
A tree structure has the two features below.
Look at the nodes surrounded by the orange square. We find that 9 is larger than both of 2 and 3, so these three nodes don’t satisfy the heap property (The value of node should be less than or equal to the values of its child nodes). Please check the orange nodes below.
However, look at the blue nodes. These nodes satisfy the heap property.
Let’s check the way how min_heapify works by producing a heap from the tree structure above. First, we call min_heapify(array, 2) to exchange the node of index 2 with the node of index 4.
After apply min_heapify(array, 2) to the subtree, the subtree changes below and meets the heap property. This subtree colored blue.
If the subtree exchanged the node of index 2 with the node of index5, the subtree won’t meet the heap property like below. So the subtree exchange the node has the smallest value in the subtree with the parent node to satisfy the heap property.
Get back to the tree correctly exchanged. When we look at the orange nodes, this subtree doesn’t satisfy the heap property.
So call min_heapify(array, 4) to make the subtree meet the heap property.
This function iterates the nodes except the leaf nodes with the for-loop and applies min_heapify to each node. We don’t need to apply min_heapify to the items of indices after n/2+1, which are all the leaf nodes. We apply min_heapify in the orange nodes below.
The time complexities of min_heapify in each depth are shown below. The number of the nodes is also showed in right.
From the figure, the time complexity of build_min_heap will be the sum of the time complexity of inner nodes. The final time complexity becomes:
The sum of the number of nodes in each depth will become n. So we will get this equation below.
The equation above stands for the geometric sequence, so we can deform it and get the height of the tree as follow: