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).keyand 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[1]
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[1]
H[1] = 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()inHeapInsert()is thatMaxHeapify()is a top-down approach whileHeapIncreaseKey()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 useHeapInscreaseKey()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
HeapMaximum(): \(T(n) = \Theta(1)\)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[0]
def extract_max(self):
max = self.array[0]
self.array[0] = 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[0], self.array[i] = self.array[i], self.array[0]
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")
}
}
Leave a comment