论坛 › 数据结构与算法 › 优先队列以及堆排序(C++)

andalousie 发表于 2014-2-12 11:00:53

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

最大优先队列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 < _pq; }
        void swap(int i, int j)
        {
                T ex   = _pq;
                _pq = _pq;
                _pq = ex;
        }
};

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

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;
        swap(1, _N--);
        sink(1);
        _pq = 0;
        return max;
}

#endif堆排序（注意排序从a开始，a不参与。）

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 < a; }
        void swap(T a[], int i, int j)
        {
                T ex = a;
                a = a;
                a = ex;
        }
};

#endif

yuzhouliu2000 发表于 2014-2-28 11:57:19

太感谢了，楼主好人

cable5881 发表于 2014-8-12 09:27:49

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

jsqking99 发表于 2014-8-27 00:05:38

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

irvine726 发表于 2014-8-28 09:24:48

支持楼主~

郭兴华 发表于 2014-8-31 10:24:08

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

ゃ莼处狼性ぉ 发表于 2014-8-31 10:55:44

支持楼主

郭兴华1 发表于 2014-8-31 12:34:49

强烈支持楼主ing……

查看完整版本: 优先队列以及堆排序(C++)