Swift implementation of the heapsort algorithm code example

  • 2020-05-13 03:31:52
  • OfStack

Algorithm thought
Heapsort takes advantage of the maximum (or minimum) keyword of the maximum heap (or small root heap) heap top record, making it easy to select the record with the maximum (or minimum) keyword in the current unordered area.
1. The basic idea of sorting by maximum heap
(1) build the initial file R[1..n] into a maximum heap, which is the initial unordered area
(2) the record R[1] (that is, the top of the heap) and the last record R[n] are exchanged to obtain the new disordered area R[1.. n-1] and ordered area R[n].keys≤R[n].key
(3) since the new root R[1] may violate the nature of the heap after the swap, the current disordered area R[1.. n-1] should be adjusted to the heap. Then, R[1], the largest record of the keyword in R[1.. n-1], and R[n-1], the last record between the two, are exchanged again to obtain a new disordered area, R[1.. n-2], and R[n-2].keys≤R[n-1..n]. Again, adjust R[1.. n-2] to the heap.
...
Until the unordered region has only one element.
2. Basic operation of maximum heap sorting algorithm:
(1) build a heap. Build a heap is a process of constantly adjusting the heap, starting from len/2 and going from 1 to the first node, where len is the number of elements in the heap. The process of building the heap is a linear process, and the process of adjusting the heap is directly called from len/2 to 1 at 0, which is equivalent to o(h1)+o(h2)... +o(hlen/2), where h represents the depth of nodes, len/2 represents the number of nodes, which is a summation process, and the result is a linear O(n).
(2) tuning heap: tuning heap is used in the process of building the heap, and it is also used in the process of sorting the heap. The idea is to compare the node i with its child node left(i),right(i), select the three largest (or smallest), if the maximum (small) value is not the node i but one of its child nodes, the interactive node i and the node, and then call the adjustment heap process, which is a recursive process. The process time complexity of adjusting the heap is related to the depth of the heap and is the operation of lgn, because it is adjusted along the direction of the depth.
(3) heap sort: heap sort is carried out by using the above two processes. The first is to build the heap based on the elements. The root node of the heap is then taken out (1 is usually swapped with the last node), the previous len-1 node continues the process of heap adjustment, and the root node is taken out again, so that the 1 is taken out until all the nodes are taken out. The time complexity of the heapsort process is O(nlgn). Because the time complexity of building the heap is O(n) (call once); The time complexity of adjusting the heap is lgn, and n-1 is called once, so the time complexity of heap sort is O(nlgn)[2]
Pay attention to
(1) just do n-1 sorting, and select the larger n-1 keyword to make the file increment orderly.
(2) sorting with a small root heap is similar to using a maximum heap, except that the sorting results are in descending order. Heapsort is the opposite of direct selection sort: the unordered region in a heapsort always precedes the ordered region at any given moment, and the ordered region extends from the tail of the original vector to the entire vector

Swift sample
(1) realize ascending sorting based on the maximum heap


func initHeap(inout a: [Int]) {
 for var i = (a.count - 1) / 2; i >= 0; --i {
  adjustMaxHeap(&a, len: a.count, parentNodeIndex: i)
 }
}
 
func adjustMaxHeap(inout a: [Int], len: Int, parentNodeIndex: Int) {
 //  if len <= 0 , indicating that the disordered area has been reduced to 0
 guard len > 1 else {
  return
 }
 
 //  Left and right child indexes of the parent 
 let leftChildIndex = 2 * parentNodeIndex + 1
 
 //  If you don't even have a left child,  1 There must be no right child, which means there is no need to go down 
 guard leftChildIndex < len else {
  return
 }
 
 let rightChildIndex = 2 * parentNodeIndex + 2
 
 //  An index used to record children that need to be swapped with their parents 
 var targetIndex = -1
 
 //  If there is no right child, but there is a left child, you can only choose the left child 
 if rightChildIndex > len {
  targetIndex = leftChildIndex
 } else {
  //  You have left and right children, and you need to find the biggest 1 a 
  targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex
 }
 
 //  Only the child is bigger than the parent and needs to be swapped 
 if a[targetIndex] > a[parentNodeIndex] {
  let temp = a[targetIndex]
  
  a[targetIndex] = a[parentNodeIndex]
  a[parentNodeIndex] = temp
  
  //  Since the nature of the new subtree stack may be destroyed after the swap, it needs to be adjusted a[targetIndex] Is a child tree of the parent to satisfy the nature of the heap 
  adjustMaxHeap(&a, len: len, parentNodeIndex: targetIndex)
 }
}
 
func maxHeapSort(inout a: [Int]) {
 guard a.count > 1 else {
  return
 }
 
 initHeap(&a)
 
 for var i = a.count - 1; i > 0; --i {
  //  every 1 Each trip swaps the top of the heap to the end of the specified range 1 A position 
  if a[0] > a[i] {
   let temp = a[0]
   
   a[0] = a[i]
   a[i] = temp
  }
  print(a)
  print(i - 1)
  //  Ordered length +1 And the length of the disordered region -1 I'm going to continue to reduce the disorder, so i-1
  //  The top of the heap is always there 0 So the parent can be adjusted from the top of the heap 
  adjustMaxHeap(&a, len: i - 1, parentNodeIndex: 0)
  print(a)
 }
}


(2) sort in descending order based on minimum heap


func initHeap(inout a: [Int]) {
 for var i = (a.count - 1) / 2; i >= 0; --i {
  adjustMinHeap(&a, len: a.count, parentNodeIndex: i)
 }
}
 
func adjustMinHeap(inout a: [Int], len: Int, parentNodeIndex: Int) {
 //  if len <= 0 , indicating that the disordered area has been reduced to 0
 guard len > 1 else {
  return
 }
 
 //  Left and right child indexes of the parent 
 let leftChildIndex = 2 * parentNodeIndex + 1
 
 //  If you don't even have a left child,  1 There must be no right child, which means there is no need to go down 
 guard leftChildIndex < len else {
  return
 }
 
 let rightChildIndex = 2 * parentNodeIndex + 2
 
 //  An index used to record children that need to be swapped with their parents 
 var targetIndex = -1
 
 //  If there is no right child, but there is a left child, you can only choose the left child 
 if rightChildIndex > len {
  targetIndex = leftChildIndex
 } else {
  //  You have left and right children, and you need to find the biggest 1 a 
  targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex
 }
 
 //  Only the child is bigger than the parent and needs to be swapped 
 if a[targetIndex] < a[parentNodeIndex] {
  let temp = a[targetIndex]
  
  a[targetIndex] = a[parentNodeIndex]
  a[parentNodeIndex] = temp
  
  //  Since the nature of the new subtree stack may be destroyed after the swap, it needs to be adjusted a[targetIndex] Is a child tree of the parent to satisfy the nature of the heap 
  adjustMinHeap(&a, len: len, parentNodeIndex: targetIndex)
 }
}
 
func minHeapSort(inout a: [Int]) {
 guard a.count > 1 else {
  return
 }
 
 initHeap(&a)
 
 for var i = a.count - 1; i > 0; --i {
  //  every 1 Each trip swaps the top of the heap to the end of the specified range 1 A position 
  if a[0] < a[i] {
   let temp = a[0]
   
   a[0] = a[i]
   a[i] = temp
  } else {
    return //  You can just exit, because it's all sorted 
  }
  
  //  Ordered length +1 And the length of the disordered region -1 I'm going to continue to reduce the disorder, so i-1
  //  The top of the heap is always there 0 So the parent can be adjusted from the top of the heap 
  adjustMinHeap(&a, len: i - 1, parentNodeIndex: 0)
 }
}

Testing:


var arr = [5, 3, 8, 6, 4]
//var arr = [89,-7,999,-89,7,0,-888,7,-7]
maxHeapSort(&arr)
 
print(arr)
 
//  The print log is 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]


Related articles: