Chapter 6 Heapsort

6.1 Heaps

Heapsort 堆排序

Running time: \(\Theta(nlgn)\)

Using a data structure "heap" to manage information

It can be used in both heapsort and priority queue

6.2 Maintaining the heap property

6.5 Priority queues

A max-priority quese supports the following operations:

• MAXIMUM(S): returns the element of S with the largest key.
• EXTRACT-MAX(S): removes and returns the element of S with the largest key.
• INCREASE-KEY(S, i, k): increases the value of element i's key to the new value k, which is assumed to be at least as large as i's current key value.
• INSERT(S, x): inserts the element x into the set S, which is equivalent to the operation S = S \vee {x}.