Are priority queue only a min or max heap ?

Heap sorting utilizes the feature of the largest (or smallest) key of the top record of the large root heap (or small root heap), making it simple to select the largest (or smallest) key record in the current disordered area.

(1) The basic idea of ​​sorting with big root heap

① First build the initial file R[1..n] into a large root pile, which is the initial disordered area

② Exchange the record R[1] with the largest keyword (that is, the top of the heap) with the last record R[n] of the disordered area, thereby obtaining a new disordered area R[1..n-1] and Sequence area R[n], and satisfies R[1..n-1].keys≤R[n].key

③Because the new root R[1] may violate the nature of the heap after the exchange, the current disordered area R[1..n-1] should be adjusted to the heap. Then exchange the record R[1] with the largest keyword in R[1..n-1] again with the last record R[n-1] of the interval, thereby obtaining a new disordered area R[1.. n-2] and the ordered area R[n-1..n], and still satisfy the relationship R[1..n-2].keys≤R[n-1..n].keys, also need R [1..n-2] Adjusted to heap.

...

Until there is only one element in the disordered area.

(2) The basic operation of the big root heap sorting algorithm:

① Initialization operation: Construct R[1..n] as the initial heap;

② The basic operation of each sorting: exchange the top record R[1] of the current disordered area with the last record of the interval, and then adjust the new disordered area to a heap (also known as a rebuild heap).

note:

① Only need to do n-1 sorting, and select the larger n-1 keywords to make the files increase in order.

② Sorting with a small root heap is similar to using a large root heap, except that the sorting result is in decreasing order. Heap sorting is the opposite of direct selection sorting: the unordered area is always before the ordered area in the heap sorting at any time, and the ordered area is from the end of the original vector to the back