你的位置:首页 > ASP.net教程

[ASP.net教程]HeapSort 堆排序 基于伪代码实现


 此文原创, http://www.cnblogs.com/baokang/p/4735431.html ,禁止转载

GIF 动态图 

 

 

伪代码

/* From Wikipedia, the free encyclopedia */

1.父子节点特征

iParent = floor((i-1) / 2);
iLeftChild = 2*i + 1;
iRightChild = 2*i + 2;

2.算法伪代码

/* 保持原汁原味就不翻译了 =。= */

procedure heapsort(a, count) is  input: an unordered array a of length count   (Build the heap in array a so that largest value is at the root)  heapify(a, count)  (The following loop maintains the invariants that a[0:end] is a heap and every element   beyond end is greater than everything before it (so a[end:count] is in sorted order))  end ← count - 1  while end > 0 do    (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)    swap(a[end], a[0])    (the heap size is reduced by one)    end ← end - 1    (the swap ruined the heap property, so restore it)    siftDown(a, 0, end)
(Put elements of 'a' in heap order, in-place)procedure heapify(a, count) is  (start is assigned the index in 'a' of the last parent node)  (the last element in a 0-based array is at index count-1; find the parent of that element)  start ← floor ((count - 2) / 2)    while start ≥ 0 do    (sift down the node at index 'start' to the proper place such that all nodes below     the start index are in heap order)    siftDown(a, start, count - 1)    (go to the next parent node)    start ← start - 1  (after sifting down the root all nodes/elements are in heap order)(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)procedure siftDown(a, start, end) is  root ← start  while root * 2 + 1 ≤ end do  (While the root has at least one child)    child ← root * 2 + 1    (Left child)    swap ← root        (Keeps track of child to swap with)    if a[swap] < a[child]      swap ← child    (If there is a right child and that child is greater)    if child+1 ≤ end and a[swap] < a[child+1]      swap ← child + 1    if swap = root      (The root holds the largest element. Since we assume the heaps rooted at the       children are valid, this means that we are done.)      return    else      swap(a[root], a[swap])      root ← swap      (repeat to continue sifting down the child now)

Java实现

 

 1   public void heapsort(int[] a, int count) { 2     if (count < 2) 3       return; 4     heapify(a, count); 5     int end = count - 1; 6     while (end > 0) { 7       swap(a, 0, end); 8       end--; 9       siftdown(a, 0, end);10     }11   }12   public void heapify(int[] a, int count) {13     int start = (count - 2) / 2;14     while (start >= 0) {15       siftdown(a, start, count - 1);16       start--;17     }18   }19   public void siftdown(int[] a, int start, int end) {20     int root = start;21 22     while (root * 2 + 1 <= end) {23       int child = root * 2 + 1;24       int swap = root;25 26       if (a[swap] < a[child]) {27         swap = child;28       }29       if (child + 1 <= end && a[swap] < a[child + 1]) {30         swap = child + 1;31       }32       if (root == swap) {33         return;34       } else {35         swap(a, root, swap);36       }37       root = swap;38     }39   }40   public void swap(int[] a, int i, int j) {41     int t = a[i];42     a[i] = a[j];43     a[j] = t;44   }