# Priority Queue (Using Max-Heap)

Updated:

⚠️ This post was created when I was in high school and is no longer maintained.

## 1. Intuition

• We only need to ensure that node.key < parent(node).key and do not care about the order between siblings.
• When a new node is added to the heap, we let it bubble upwards from the bottom (leaves) all the way up to the position where node.key < parent(node).key

## 2. Pseudocode

function Left(i):
return i * 2
function Right(i):
return i * 2 + 1
function Parent(i):
return floor(i/2)

algorithm BuildMaxHeap(A):
H.heap_size = A.length
For i := floor(length/2) downto 1 do
MaxHeapify(H, i)

algorithm HeapMaximum(H):
return H

algorithm MaxHeapify(H, parent): # top-down approach
left := Left(parent)
right := Right(parent)

largest := parent
if left < H.heap_size and H[left] > H[largest] then
largest = left
if right < H.heap_size and H[right] > H[largest] then
largest = right

if largest != parent then
Exchange H[parent] with H[largest]
MaxHeapify(H, largest)
--> the H[largest] now becomes smaller so we need to make sure the correct max-heap property at H[leargest] again

algorithm HeapExtractMax(H):
if H.heap_size < 1 then
throw HeapUnderFlow

max := H
H = H[H.heap_size] --> replace the root by the last node
H.heap_size -= 1
MaxHeapify(H, 1)
return max

algorithm HeapIncreaseKey(H, i, key):
if H[i] > key then
return Error("new key is smaller than the current key")

H[i] = key
While i > 1 and H[i] > H[Parent[i]] do --> bottom-up
Exchange H[i] with H[Parent[i]]
i = Parent[i]

algorithm HeapInsert(H, key):
H.heap_size += 1
-- H[heap_size] = key
-- MaxHeapify(H[heap_size]) ??? No, we have to bottom-up
H[heap_size] = -Infi
HeapIncreaseKey(H, H.heap_size, key)



Tips:

• The reason why we cannot use MaxHeapify() in HeapInsert() is that MaxHeapify() is a top-down approach while HeapIncreaseKey() is a bottom-up process which allows new nodes to bubble upwards.
• The HeapIncreaseKey() has to be the bottom-up manner in the sense that we always insert a new key at the end of the heap (array)
• In HeapInsert(), the inserted new node is always appended as a leaf first so we have to use HeapInscreaseKey() to put the new node into its right position
• Before we do HeapIncreaseKey(), we have to make sure that the key that we want to update is greater than the original one, otherwise, there is no meaning to do bubble-up maintains.

## 3. Time complexity

1. HeapMaximum(): $T(n) = \Theta(1)$
2. MaxHeapify() == HeapExtractMax() == HeapIncreaseKey() == HeapInsert(): $T(n) = O(lgn)$ ***

## 4. Code

# Python
import math

class MaxHeap:
def __init__(self, array):
self.array = array
self.size  = len(array)

self._build_max_heap_()

def __str__(self):
return str(self.array[:self.size]).strip('[]')

def _left_(self, i):
return i * 2
def _right_(self, i):
return i * 2 + 1
def _parent_(self, i):
return i // 2

def _build_max_heap_(self):
for i in range(math.floor(len(self.array) / 2), -1, -1):
self.maxheapify(i)

def maxheapify(self, parent): # top-down approach
left  = self._left_(parent)
right = self._right_(parent)

largest = parent
if left < self.size and self.array[left] > self.array[largest]: # ???
largest = left
if right < self.size and self.array[right] > self.array[largest]:
largest = right
if largest != parent:
# make sure that the root (array[i]) is now greater than all its childrens
self.array[parent], self.array[largest] = self.array[largest], self.array[parent]
self.maxheapify(largest)
'''
After exchange, the node with 'largest' index is no longer
the largest element (smaller than before) so we need to use maxheapify()
to guarrantee its max-heap property
'''

def maximum(self):
return self.array

def extract_max(self):
max = self.array
self.array = self.array[self.size-1]
self.size -= 1
self.maxheapify(0)

return max

def increase_key(self, i, key):
'''
We have to make sure the key value is greater than its original value
because this is an upwards method which means we assume the key is greater than
all the values of nodes that below i
'''
if self.array[i] > key:
raise ValueError("New key is smaller than the current key !")

self.array[i] = key
while i >= 0 and self.array[i] > self.array[self._parent_(i)]:
self.array[i], self.array[self._parent_(i)] \
= self.array[self._parent_(i)], self.array[i]
i = self._parent_(i)

def insert(self, key):
self.size += 1
if self.size > len(self.array):
self.array.append(-float("inf"))
else:
self.array[self.size-1] = -float('inf')
self.increase_key(self.size-1, key)

def heap_sort(self):
size_ = self.size
for i in range(self.size-1, -1, -1):
self.array, self.array[i] = self.array[i], self.array
self.size -= 1
self.maxheapify(0)
self.size = size_

if __name__ == "__main__":
# array = [4234,23,231412,234,-134,123,41,578,-342,55,0.9323,0.325]
array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
maxheap = MaxHeap(array)
print('Build Max Heap: ', maxheap)
print('Maximum: ', maxheap.maximum())
maxheap.insert(-11)
print('After insertion: ', maxheap)
maxheap.increase_key(3, 99999999)
print('After increasing key: ', maxheap)
print('Extract: ', maxheap.extract_max())
print('After Extraction: ', maxheap)
maxheap.heap_sort()
print('After HeapSort: ', maxheap)

// Scala
import scala.math._

class MaxHeap(array: Array[Double]) {

private val _array = array
private var _size  = array.length

_buildMaxHeap_()
private def _right_(i: Int): Int = i * 2
private def _left_(i: Int): Int = i * 2 + 1
private def _parent_(i: Int): Int = floor(i / 2).toInt
override def toString: String = s"[Max Heap]: ${this._array.slice(0,_size).mkString(", ")}" private def _swap_(i: Int, j: Int) { var tmp = 0.0 tmp = _array(i) _array(i) = _array(j) _array(j) = tmp } private def _buildMaxHeap_() { var i = 0 for (i <- floor(_size / 2).toInt to 0 by -1) { _maxHeapify_(i) } } private def _maxHeapify_(i: Int) { val left = _left_(i) val right = _right_(i) var largest = i if (left < _size && _array(left) > _array(largest)) { largest = left } if (right < _size && _array(right) > _array(largest)) { largest = right } if (largest != i) { _swap_(i, largest) _maxHeapify_(largest) } } def maximum: Double = _array(0) def extractMax: Double = { var max = _array(0) _array(0) = _array(_size-1) _size -= 1 _maxHeapify_(0) return max } def increaseKey(i: Int, key: Double) = { var index = i if (key < _array(index)) { throw new Exception("\nNew key is smaller than current key !\n") } _array(index) = key while (index > 0 && _array(index) > _array(_parent_(index))) { _swap_(index, _parent_(index)) index = _parent_(index) } } def insert(key:Double) { _size += 1 if (_size > _array.length) { _array :+ Double.NegativeInfinity } else { _array(_size-1) = Double.NegativeInfinity } increaseKey(_size-1, key) } def heapSort = { var i = 0 var tmp = _size for (i <- _size-1 to 0 by -1) { _swap_(i, 0) _size -= 1 _maxHeapify_(0) } _size = tmp } } object MaxHeapStructure { def main (args: Array[String]) : Unit = { // val array = Array(4234,3234,234234,23,234,-134,4123,41,578,-342,55,0.2323,0.325) val array = Array(0.0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10) val maxheap = new MaxHeap(array) println(s"Build Max Heap:$maxheap")
println(s"Maximum: ${maxheap.maximum}") println(s"Extract Max:${maxheap.extractMax}")
println(s"After extraction: $maxheap") maxheap.insert(-11) println(s"After insertion:$maxheap")
maxheap.increaseKey(3, 999999)
println(s"After increasing key: $maxheap") maxheap.heapSort println(s"After heap sort:$maxheap")
}
}


Tags: