Data structure: Heap

presention: Json

reference book: Introduction To Algorithms 3rd edition

book authors: Thomas H. Cormen,Charles E. Leiserson,

Ronald L. Rivest , Clifford Steim

​

Heap

The (binary) heap data structure is an array object

that we can view as a complete binary tree.

Each node of the tree corresponds to an element of the array.

​

Heap( Graph)

Node index Relation(zero base)

Parent(i):

return Math.ceil(i/2) - 1

Left(i):

return 2*(i +1) -1

Right(i):

return 2*(i+1)

Heap property

Each node in heap must satisfy Heap property.

Max-heap property: for each node in Heap A

A[Parent(i)] >= A[i], then Heap A is max-heap

Min-heap property: for each node in Heap A

A[Parent(i)] <= A[i], then Heap A is min-heap

Max-Heapify(A, i)

l = Left(i), r = Right(i), largest = 0

if l <= A.length and A[l] >= A[i]

largest = l

else largest = r

if r <= A.length and A[r] >= A[largest]

largest = r

if largest !== i

exchange A[i] with A[largest]

Max-Heapify(A, largest)

​

max-heapify Example

Build-max-heap(A)

for i = Math.floor(A.length/2) downto 0

Max-Heapify(A, i)

HeapSort(A)

Build-max-heap(A)

for i = A.length-1 downto 1

exchange A[0] with A[i]

remove last element of A

Max-heapify(A, 0)

Heap-extract-max(A)

if A.length == 0

throw “heap overflow”

max = A[0]

A[0] = A[A.length-1]

remove last element of A

Max-heapify(A, 0)

return max

Max-heap-increase-key(A, i, key)

A[i] = key

while i > 0 and A[Parent(i)] < A(i)

exchange A[i] with A[Parent(i)]

i = Parent(i)

Max-heap-insert(A, key)

append key to last element of A

Heap-increase-key(A, A.length-1, key)