优先队列以及堆排序(C++)

andalousie

最大优先队列PQ.h

1. #if !defined (PQ_H)
   
2. #define PQ_H
   
3. 
   
4. template<class T>
   
5. class PriorityQueue{
   
6. private:
   
7.         T    *_pq;
   
8.         int  _N = 0;
   
9. public:
   
10.         PriorityQueue(int capacity);
    
11.         ~PriorityQueue();
    
12.         bool isEmpty() { return _N == 0; }
    
13.         void insert(T x);
    
14.         T    pop();
    
15. private:
    
16.         void swim(int k);
    
17.         void sink(int k);
    
18.         bool less(int i, int j) { return _pq[i] < _pq[j]; }
    
19.         void swap(int i, int j)
    
20.         {
    
21.                 T ex   = _pq[i];
    
22.                 _pq[i] = _pq[j];
    
23.                 _pq[j] = ex;
    
24.         }
    
25. };
    
26. 
    
27. template<class T>
    
28. PriorityQueue<T>::PriorityQueue(int capacity)
    
29. {
    
30.         _pq = new T[capacity+1];
    
31. }
    
32. 
    
33. template<class T>
    
34. PriorityQueue<T>::~PriorityQueue(void)
    
35. {
    
36.         delete [] _pq;
    
37. }
    
38. 
    
39. template<class T>
    
40. void PriorityQueue<T>::swim(int k)
    
41. {
    
42.         while (k > 1 && less(k/2, k))
    
43.         {
    
44.                 swap(k, k/2);
    
45.                 k = k/2;
    
46.         }
    
47. }
    
48. 
    
49. template<class T>
    
50. void PriorityQueue<T>::insert(T x)
    
51. {
    
52.         _pq[++_N] = x;
    
53.         swim(_N);
    
54. }
    
55. 
    
56. template<class T>
    
57. void PriorityQueue<T>::sink(int k)
    
58. {
    
59.         while (2*k <= _N)
    
60.         {
    
61.                 int j = 2*k;
    
62.                 if (j < _N && less(j, j+1)) j++;
    
63.                 if (!less(k, j)) break;
    
64.                 swap(k, j);
    
65.                 k = j;
    
66.         }
    
67. }
    
68. 
    
69. template<class T>
    
70. T PriorityQueue<T>::pop()
    
71. {
    
72.         T max = _pq[1];
    
73.         swap(1, _N--);
    
74.         sink(1);
    
75.         _pq[_N+1] = 0;
    
76.         return max;
    
77. }
    
78. 
    
79. #endif

复制代码

堆排序（注意排序从a[1]开始，a[0]不参与。）

Heap.h

1. #if !defined (HEAP_H)
   
2. #define HEAP_H
   
3. 
   
4. template<class T>
   
5. class Heap{
   
6. public:
   
7.         void sort(T a[], int n)
   
8.         {
   
9.                 int N = n;
   
10.                 for (int k = N/2; k >= 1; --k)
    
11.                         sink(a, k, N);
    
12.                 while (N > 1)
    
13.                 {
    
14.                         swap(a, 1, N);
    
15.                         sink(a, 1, --N);
    
16.                 }
    
17.         }
    
18. private:
    
19.         void sink(T a[], int k, int N)
    
20.         {
    
21.                 while (2*k <= N)
    
22.                 {
    
23.                         int j = 2*k;
    
24.                         if (j < N && less(a, j, j+1)) j++;
    
25.                         if (!less(a, k, j)) break;
    
26.                         swap(a, k, j);
    
27.                         k = j;
    
28.                 }
    
29.         }
    
30.         bool less(T a[], int v, int w)
    
31.         { return a[v] < a[w]; }
    
32.         void swap(T a[], int i, int j)
    
33.         {
    
34.                 T ex = a[i];
    
35.                 a[i] = a[j];
    
36.                 a[j] = ex;
    
37.         }
    
38. };
    
39. 
    
40. #endif

复制代码

yuzhouliu2000

太感谢了，楼主好人

cable5881

谢谢楼主分享！！！！！！！！

jsqking99

感谢楼主无私分享！！！！！！

irvine726

支持楼主~

郭兴华

支持小甲鱼！！支持小甲鱼！！

ゃ莼处狼性ぉ

支持楼主

郭兴华1

强烈支持楼主ing……