Priority Queue (Using Max-Heap)
Created:
⚠️ 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, let it bubble up from the leaves until it reaches a spot 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:
- We cannot use
MaxHeapify()inHeapInsert()becauseMaxHeapify()is top-down, whileHeapIncreaseKey()is bottom-up and lets new nodes bubble up. HeapIncreaseKey()must work bottom-up since we always append new keys to the end of the heap.- In
HeapInsert(), the new node starts as a leaf, so we callHeapIncreaseKey()to move it to the right spot. - Before calling
HeapIncreaseKey(), the new key must be greater than the existing one; otherwise bubbling up is pointless.
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