Algorithm Thought
Heap sorting takes advantage of the maximum (or minimum) keyword record of the maximum heap (or small root heap), making it simple to select the record of the largest (or minimum) keyword in the current unordered area.
1. The basic idea of sorting with the largest heap
(1) First build the initial file R[1..n] into a maximum heap, which is the initial unordered area
(2) The record R[1] with the largest keyword (i.e. the top of the heap) is exchanged with the last record R[n] of the disordered area, thereby obtaining the new disordered area R[1..n-1] and ordered area R[n], and satisfying R[1..n-1].keys≤R[n].key
(3) Since the new root R[1] after exchange may violate the heap nature, the current unordered area R[1..n-1] should be adjusted to the heap. Then, the record R[1] with the largest keyword in R[1..n-1] is exchanged again with the last record R[n-1] of this interval, thereby obtaining the new unordered 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, and R[1..n-2] should also be adjusted to the heap.
……
Until there is only one element in the unordered area.
2. Basic operations of the maximum heap sorting algorithm:
(1) Build the heap. Build the heap is a process of constantly adjusting the heap, starting from len/2 to the first node, where len is the number of elements in the heap. The heap construction process is a linear process. The process of adjusting the heap is called from len/2 to 0, which is equivalent to o(h1)+o(h2)…+o(hlen/2) where h represents the depth of the node and len/2 represents the number of nodes. This is a summing process, and the result is linear O(n).
(2) Adjust the heap: Adjust the heap will be used during the heap construction process, and will also be used during the heap sorting process. The idea used is to compare node i with its child node left(i), right(i), and select the largest (or smallest) of the three. If the maximum (small) value is not node i but one of its child nodes, interact with node i and the node, and then call the adjustment heap process. This is a recursive process. The process time complexity of the adjustment heap is related to the depth of the heap. It is an operation of lgn because it is adjusted along the depth direction.
(3) Heap sorting: Heap sorting is carried out using the above two processes. The first is to build the heap based on the elements. Then take out the root node of the heap (usually exchanged with the last node), continue the heap adjustment process of the previous len-1 nodes, and then take out the root node, so that all nodes are removed. The time complexity of the heap sorting process is O(nlgn). Because the time complexity of building the heap is O(n) (called once); the time complexity of adjusting the heap is lgn, and n-1 times is called, so the time complexity of heap sort is O(nlgn)[2]
Notice
(1) Just do n-1 ordering and select larger n-1 keywords to make the file incrementally and orderly.
(2) Sort with small root heaps is similar to using the largest heaps, except that the sorting results are decreasing and orderly. Heap sorting is the opposite of direct selection sorting: at any time the unordered area is always before the ordered area, and the ordered area is gradually expanded from behind to forward to the entire vector at the end of the original vector.
Swift example
(1) Implement ascending sorting based on the maximum heap
func initHeap(inout a: [Int]) {
for var i = ( - 1) / 2; i >= 0; --i {
adjustMaxHeap(&a, len: , parentNodeIndex: i)
}
}
func adjustMaxHeap(inout a: [Int], len: Int, parentNodeIndex: Int) {
// If len <= 0, it means that the unordered area has been reduced to 0 guard len > 1 else {
return
}
// Index of left and right children of parent node let leftChildIndex = 2 * parentNodeIndex + 1
// If you don’t even have a left child, you must have no right child, which means you don’t need to go any further guard leftChildIndex < len else {
return
}
let rightChildIndex = 2 * parentNodeIndex + 2
// Used to record the index of the child that needs to be exchanged with the parent node var targetIndex = -1
// If there is no right child but the left child, you can only choose the left child if rightChildIndex > len {
targetIndex = leftChildIndex
} else {
// There are children on the left and right, so you need to find the largest one targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex
}
// Only children are bigger than the father's node and need to be exchanged if a[targetIndex] > a[parentNodeIndex] {
let temp = a[targetIndex]
a[targetIndex] = a[parentNodeIndex]
a[parentNodeIndex] = temp
// Since the properties of the new subtree heap may be destroyed after exchange, the child tree with a[targetIndex] as the parent node needs to be adjusted to satisfy the properties of the heap adjustMaxHeap(&a, len: len, parentNodeIndex: targetIndex)
}
}
func maxHeapSort(inout a: [Int]) {
guard > 1 else {
return
}
initHeap(&a)
for var i = - 1; i > 0; --i {
// Each trip swaps the top of the heap to the last position within the specified range if a[0] > a[i] {
let temp = a[0]
a[0] = a[i]
a[i] = temp
}
print(a)
print(i - 1)
// The length of the ordered area +1, while the length of the unordered area -1, continues to narrow the disordered area, so i-1 // The heap top is always at position 0, so the parent node adjustment can start from the heap top adjustMaxHeap(&a, len: i - 1, parentNodeIndex: 0)
print(a)
}
}
(2) Sort based on the minimum heap descending order
func initHeap(inout a: [Int]) {
for var i = ( - 1) / 2; i >= 0; --i {
adjustMinHeap(&a, len: , parentNodeIndex: i)
}
}
func adjustMinHeap(inout a: [Int], len: Int, parentNodeIndex: Int) {
// If len <= 0, it means that the unordered area has been reduced to 0 guard len > 1 else {
return
}
// Index of left and right children of parent node let leftChildIndex = 2 * parentNodeIndex + 1
// If you don’t even have a left child, you must have no right child, which means you don’t need to go any further guard leftChildIndex < len else {
return
}
let rightChildIndex = 2 * parentNodeIndex + 2
// Used to record the index of the child that needs to be exchanged with the parent node var targetIndex = -1
// If there is no right child but the left child, you can only choose the left child if rightChildIndex > len {
targetIndex = leftChildIndex
} else {
// There are children on the left and right, so you need to find the largest one targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex
}
// Only children are bigger than the father's node and need to be exchanged if a[targetIndex] < a[parentNodeIndex] {
let temp = a[targetIndex]
a[targetIndex] = a[parentNodeIndex]
a[parentNodeIndex] = temp
// Since the properties of the new subtree heap may be destroyed after exchange, the child tree with a[targetIndex] as the parent node needs to be adjusted to satisfy the properties of the heap adjustMinHeap(&a, len: len, parentNodeIndex: targetIndex)
}
}
func minHeapSort(inout a: [Int]) {
guard > 1 else {
return
}
initHeap(&a)
for var i = - 1; i > 0; --i {
// Each trip swaps the top of the heap to the last position within the specified range if a[0] < a[i] {
let temp = a[0]
a[0] = a[i]
a[i] = temp
} else {
return // You can exit directly because it is already in order }
// The length of the ordered area +1, while the length of the unordered area -1, continues to narrow the disordered area, so i-1 // The heap top is always at position 0, so the parent node adjustment can start from the heap top adjustMinHeap(&a, len: i - 1, parentNodeIndex: 0)
}
}
test:
var arr = [5, 3, 8, 6, 4] //var arr = [89,-7,999,-89,7,0,-888,7,-7] maxHeapSort(&arr) print(arr) // Print the log as follows:[4, 6, 5, 3, 8] 3 [6, 4, 5, 3, 8] [3, 4, 5, 6, 8] 2 [5, 4, 3, 6, 8] [3, 4, 5, 6, 8] 1 [3, 4, 5, 6, 8] [3, 4, 5, 6, 8] 0 [3, 4, 5, 6, 8] [3, 4, 5, 6, 8]