Heaps

Heap

• almost complete binary tree
• satisfy heap property(max-heap of min-heap)
  Max-heap: Data(parent node P)>= Data (child node C)
  Min-heap: Data(parent node P)<=Data(childe node C)

Static Representation

length[A] : size of the array A
For an index node i
parent(i): return [i/2]
left(i): return (2i)
right(i): return (2i+1)
Max-heap property: Value(node) >= Value (child)

 

MAX-HEAPIFY

• find the largest between root, left-childe, and right-child
  -swap root with largest

Maintaining Heap Property

MAX-HEAPIFY(A, i)
l ← left (i)
r ← right (i)
if l ≤ heapsize of A and A[l] > A[i]
largest ← l
else largest ← i
if r ≤ heapsize of A and A[r] > A[largest]
largest ← r if largest ≠ i
swap (A[i] ↔ A[largest])
MAX-HEAPIFY(A, largest)

Complexity

O(ln(n))

Building a Heap

BUILD_MAX-HEAP (A){
for i ← ⌊length[A]/2⌋ downto 1 do
	MAX-HEAPIFY(A, i) }

Complexity

O(nln(n))

Heap Sort

HEAPSORT(A)
1. 2. 3. 4. 5.
BUILD-MAX-HEAP(A)
for i<-length of A down to 2 
	exchange A[1] ↔ A[i]
	heapsize of A<-heapsize of A-1 
    MAX-HEAPIFY (A,1)

Complexity

o(nln(n))

Priority Queue

operations
Insert(A,x)
Get-max(A)
Remove-max(A)

Remove-max

GET-MAX(A) return A[1]

REMOVE-MAX(A)
1 ifheapsizeofA<1then
2 error "heap underflow"
3 max ← A[1]
4 A[1] ← A[heapsize of A]
5 heapsizeofA←heapsizeofA-1
6 MAX-HEAPIFY(A, 1)
7 return max

Insert

INSERT(A, x)
1 if heapsize of A < 1 then
2
3 else
A[1] ← x
4 5 6 7
heapsize ← heapsize of A + 1 A[heapsize] ← x
i ← heapsize
while (A[i] > parent(A[i]){
swap(A[i], A[parent(A[i])])
i ← parent(A[i]) }

Applications

• Heapsort: best sorting methods with in-place and with no quadratic worsrt-case
• selection algorithms: finding min, max, both min and max, median, or even the kth largest element can be done in lindear time(often constant time) useing heaps
• Graph algorithms: by using heaps as internal traversal data structures, run time could be reduced by polynomial order.