堆排序

  1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 #define ARR_SIZE 20
  6 
  7 void CreateRandArr(int a[]);
  8 
  9 template <typename T>
 10 class MaxPQ
 11 {
 12     private:
 13         int *ar = NULL;
 14         int N = ARR_SIZE;
 15 
 16     public:
 17         MaxPQ();
 18         MaxPQ(T ap[], int size);
 19         MaxPQ(const MaxPQ & ap);   //注意这里必须是引用
 20         bool isEmpty(){return 0 == N;}
 21         int size(void){return N;}
 22         void insert(T v);
 23         T delMax(void);
 24         void sink(int n, int size);
 25         void swim(int n);
 26         void sort(void);
 27         void exch(int m, int n){T temp = ar[m];ar[m] = ar[n]; ar[n] = temp;}
 28         void show(void);
 29         MaxPQ<T> & operator=(const MaxPQ<T> & ap);
 30         ~MaxPQ(){delete [] ar;}
 31 };
 32 
 33 template <typename T>
 34 MaxPQ<T>::MaxPQ()
 35 {
 36     ar = (int *)new int [ARR_SIZE + 1];
 37     CreateRandArr(ar+1);
 38 }
 39 
 40 template <typename T>
 41 MaxPQ<T>::MaxPQ(T ap[], int size)
 42 {
 43     N = size; 
 44     ar = (T *)new T [N + 1]; 
 45     for(int i = 1; i <= N; i++)
 46     {
 47         ar[i] = ap[i-1];
 48     }
 49 }
 50 
 51 template <typename T>
 52 MaxPQ<T>::MaxPQ(const MaxPQ & ap)
 53 {
 54     if(ap == *this)
 55         return;
 56     else
 57     {
 58         N = ap.size();
 59         ar = new T [N+1];
 60         for(int i=1;i<N;i++)
 61         {
 62             ar[i] = ap.ar[i];
 63         }
 64     }
 65 }
 66 
 67 template <typename T>
 68 MaxPQ<T> & MaxPQ<T>::operator=(const MaxPQ<T> & ap)
 69 {
 70     if(ap == *this)
 71         return this;
 72     else
 73     {
 74         delete [] ar;
 75         N = ap.N;
 76         ar = new T [N+1];
 77         for(int i=1;i<N;i++)
 78         {
 79             ar[i] = ap.ar[i];
 80         }
 81     }
 82 
 83     return *this;
 84 }
 85 
 86 template <typename T>
 87 void MaxPQ<T>::insert(T v)
 88 {
 89     ar[++N] = v; 
 90     swim(N);
 91 }
 92 
 93 template <typename T>
 94 T MaxPQ<T>::delMax(void)
 95 {
 96     T max = ar[1];
 97     ar[1] = ar[N];
 98     /* ar[N] = NULL; */
 99     sink(1, N);
100     return max;
101 }
102 
103 template <typename T>
104 void MaxPQ<T>::sink(int n, int size)
105 {
106     while(2 * n <= size)
107     {
108         int j = 2 * n;
109         if(j < size && ar[j] < ar[j+1]) j++;   // ar[2n] 和 ar[2n+1] 取较大者
110         if(ar[n] >= ar[j]) break;
111         exch(n, j);
112         n = j;
113     }
114 }
115 
116 template <typename T>
117 void MaxPQ<T>::swim(int n)
118 {
119     while(n > 1 && ar[n/2] < ar[n])
120     {
121         exch(n/2, n);
122         n = n/2;
123     }
124 }
125 
126 template <typename T>
127 void MaxPQ<T>::sort(void)
128 {
129     for(int k = N/2; k >=1; k--)
130         sink(k, N);     // 先对数组进行堆有序处理
131     int num = N;
132     while(num > 1)
133     {
134         exch(1, num--);   // 将最大元素放到当前堆的最后一个位置
135         sink(1, num);  // 利用下沉保持堆有序
136     }
137 }
138 
139 template <typename T>
140 void MaxPQ<T>::show(void)
141 {
142     for(int i=1; i<=N; i++)
143     {
144         cout << ar[i] << ' ';
145     }
146     cout << endl;
147 }
148 
149 
150 void CreateRandArr(int a[])
151 {
152     int i;
153     for(i=0;i<ARR_SIZE;i++)
154     {
155         a[i] = rand() % 100;
156         cout <<a[i] << ' ' ; 
157     }
158     cout << endl;
159 }
160 
161 int main()
162 {
163     int ar[ARR_SIZE];
164     CreateRandArr(ar);
165     MaxPQ<int> arr(ar, ARR_SIZE);    // 也可以用默认初始化
166     arr.sort();
167     cout << "after sort: " << endl;
168     arr.show();
169     
170     return 0;
171 }

上面的sink函数是否应该替换成下面这种形式？（因为j+1有可能大于size而造成越界）

 1 void sink(int a[], int k, int n)
 2 {
 3     int temp;
 4     while(2*k <= n)
 5     {
 6         if(2*k+1 <= n && a[2*k+1] > a[2*k])
 7         temp = 2*k+1;
 8         else temp = 2*k;
 9         if(a[temp] > a[k]) exchange(a, temp, k);
10         else break;
11         k = temp;
12     }
13 }