Zero Lee的专栏

堆排序算法的一个实现

Pseudcode
 1 function heapSort(a, count) is
 2      input:  an unordered array a of length count
 3  
 4      (first place a in max-heap order)
 5      heapify(a, count)
 6  
 7      end := count-1 //in languages with zero-based arrays the children are 2*i+1 and 2*i+2
 8      while end > 0 do
 9          (swap the root(maximum value) of the heap with the last element of the heap)
10          swap(a[end], a[0])
11          (put the heap back in max-heap order)
12          siftDown(a, 0, end-1)
13          (decrease the size of the heap by one so that the previous max value will
14          stay in its proper placement)
15          end := end - 1
16  
17  function heapify(a, count) is
18      (start is assigned the index in a of the last parent node)
19      start := count / 2 - 1
20      
21      while start ≥ 0 do
22          (sift down the node at index start to the proper place such that all nodes below
23           the start index are in heap order)
24          siftDown(a, start, count-1)
25          start := start - 1
26      (after sifting down the root all nodes/elements are in heap order)
27  
28  function siftDown(a, start, end) is
29      input:  end represents the limit of how far down the heap
30                    to sift.
31      root := start
32 
33      while root * 2 + 1 ≤ end do          (While the root has at least one child)
34          child := root * 2 + 1        (root*2 + 1 points to the left child)
35          swap := root        (keeps track of child to swap with)
36          (check if root is smaller than left child)
37          if a[swap] < a[child]
38              swap := child
39          (check if right child exists, and if it's bigger than what we're currently swapping with)
40          if child < end and a[swap] < a[child+1]
41              swap := child + 1
42          (check if we need to swap at all)
43          if swap != root
44              swap(a[root], a[swap])
45              root := swap          (repeat to continue sifting down the child now)
46          else
47              return
48 

C++ 实现
 1 // build one maximum heap
 2 template <typename T>
 3 void heapsort(std::vector<T>& a)
 4 {
 5     int sz = (int)a.size();
 6     for (int i = sz/2; i >= 0; i--)
 7         percDown(a, i, sz);
 8     std::cout << "build heap is done.\n";
 9     for (int j = sz-1; j > 0; j--) {
10         std::swap(a[0], a[j]);
11         percDown(a, 0, j);
12     }
13 }
14 
15 inline int leftChild(int i)
16 {
17     return 2*i+1;
18 }
19 
20 template <typename T>
21 void percDown(std::vector<T>& a, int i, int n)
22 {
23     int child;
24     T tmp;
25     for (tmp = a[i]; leftChild(i) < n; i = child) {
26         child = leftChild(i);
27         if (child != n-1 && a[child] < a[child+1])
28             child++;
29         if (tmp < a[child])
30             a[i] = a[child];
31         else
32             break;
33     }
34     a[i] = tmp;
35 }
36 

posted on 2011-03-25 09:32 Zero Lee 阅读(244) 评论(0)  编辑 收藏 引用 所属分类: Data structure and algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理