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.