MM9
Heap
partially ordered data structure that is especially suitable for implementing
priority queues.
The shape property
The parental dominance or heap property—the key in each node is greater
than or equal to the keys in its children.
properties of heaps
A node of a heap considered with all its descendants is also a heap.
A heap can be implemented as an array by recordind its elements in the top-down, left-to-right fashion.It is convenient to store the heaps's elements in positions 1 through n of such an array,leaving H[0] either unused or putting there a sentinel whose value is greater than every elementi in the heap.In such a representation.
The root of a heap always contains its largest element.
There exists exactly one essentially complete binary tree with n nodes. Its
height is equal to [log2 n]
the parental node keys will be in the first [n/2] positions of the array,
while the leaf keys will occupy the last [n/2] positions
the children of a key in the array's parental position i (1<= i <=[n/2]) will be in position 2i and 2i + 1,and, correspondingly,the parent of a key in position i (2<= i <= n) will be in position [i/2]
bottom-up heap construction
top-down heap construction
Heapsort
Stage 1
Stage 2
heap construction
maximum deletions
Construct a heap for a given array
Apply the root-deletion operation n − 1 times
to the remaining heap.