Course Data Structure

Heap

John William Joseph Williams (1929 or 1930 - September 29, 2012) was a British-born computer scientist best known for inventing in 1964 heapsort and the binary heap data structure. He spent the latter part of his career in Canada, moving to Ottawa in 1972 and working for Bell-Northern Research and Nortel before retiring in 1995.

Định nghĩa Heap

Heap là một dãy các phần tử a0, a1, ..., ar thỏa các quan hệ ∀ i ∈ [1, r]

ai ≥ a2i+1
ai ≥ a2i+2
(ai, a2i+1), (ai, a2i+2) là các cặp phần tử liên đới