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

andalousie

最大优先队列PQ.h

#if !defined (PQ_H)
#define PQ_H

template<class T>
class PriorityQueue{
private:
        T    *_pq;
        int  _N = 0;
public:
        PriorityQueue(int capacity);
        ~PriorityQueue();
        bool isEmpty() { return _N == 0; }
        void insert(T x);
        T    pop();
private:
        void swim(int k);
        void sink(int k);
        bool less(int i, int j) { return _pq[i] < _pq[j]; }
        void swap(int i, int j)
        {
                T ex   = _pq[i];
                _pq[i] = _pq[j];
                _pq[j] = ex;
        }
};

template<class T>
PriorityQueue<T>::PriorityQueue(int capacity)
{
        _pq = new T[capacity+1];
}

template<class T>
PriorityQueue<T>::~PriorityQueue(void)
{
        delete [] _pq;
}

template<class T>
void PriorityQueue<T>::swim(int k)
{
        while (k > 1 && less(k/2, k))
        {
                swap(k, k/2);
                k = k/2;
        }
}

template<class T>
void PriorityQueue<T>::insert(T x)
{
        _pq[++_N] = x;
        swim(_N);
}

template<class T>
void PriorityQueue<T>::sink(int k)
{
        while (2*k <= _N)
        {
                int j = 2*k;
                if (j < _N && less(j, j+1)) j++;
                if (!less(k, j)) break;
                swap(k, j);
                k = j;
        }
}

template<class T>
T PriorityQueue<T>::pop()
{
        T max = _pq[1];
        swap(1, _N--);
        sink(1);
        _pq[_N+1] = 0;
        return max;
}

#endif

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

Heap.h

#if !defined (HEAP_H)
#define HEAP_H

template<class T>
class Heap{
public:
        void sort(T a[], int n)
        {
                int N = n;
                for (int k = N/2; k >= 1; --k)
                        sink(a, k, N);
                while (N > 1)
                {
                        swap(a, 1, N);
                        sink(a, 1, --N);
                }
        }
private:
        void sink(T a[], int k, int N)
        {
                while (2*k <= N)
                {
                        int j = 2*k;
                        if (j < N && less(a, j, j+1)) j++;
                        if (!less(a, k, j)) break;
                        swap(a, k, j);
                        k = j;
                }
        }
        bool less(T a[], int v, int w)
        { return a[v] < a[w]; }
        void swap(T a[], int i, int j)
        {
                T ex = a[i];
                a[i] = a[j];
                a[j] = ex;
        }
};

#endif

yuzhouliu2000

太感谢了，楼主好人

cable5881

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

jsqking99

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

irvine726

支持楼主~

郭兴华

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

ゃ莼处狼性ぉ

支持楼主

郭兴华1

强烈支持楼主ing……