利用堆结构实现优先级队列

class file :

#ifndef PRIORITY_QUEUE_H_
#define PRIORITY_QUEUE_H_
#include <stdint.h>
#include <iostream>

#define EXCHANGE(a,b,t) do{t=a;a=b;b=t;}while(0)

// bMax = true  : 最大优先级队列
// bMax = false : 最小优先级队列
template<typename T,uint32_t S,bool bMax = true>
class PriorityQueue
{
public:
    PriorityQueue();
    ~PriorityQueue();
    int32_t Push(T &data);
    int32_t Pop();
    T &Front();
    bool Empty(){ return size == 0; }
    uint32_t Size(){ return size; }
public:
    void Dump(const uint32_t length = S);
private:
    void MaxHeapify(T arr[],const uint32_t size,const uint32_t i);
    void MinHeapify(T arr[],const uint32_t size,const uint32_t i);
    uint32_t Parent(uint32_t i){ return i / 2; }
    uint32_t Right(uint32_t i){ return i * 2 + 1; }
    uint32_t Left(uint32_t i){ return i * 2; }
private:
    typedef void (PriorityQueue::*Heapify)(T arr[], const uint32_t size, const uint32_t i);
    bool Less(T &left, T &right);
    T *arr;
    uint32_t size;
    Heapify pHeapify;
};

template<typename T, uint32_t S, bool bMax /*= true*/>
bool PriorityQueue<T, S, bMax>::Less(T &left, T &right)
{
    if (bMax == true)
    {
        return left < right;
    }
    return left > right;
}

template<typename T, uint32_t S, bool bMax /*= true*/>
int32_t PriorityQueue<T, S, bMax>::Pop()
{
    if (size == 0){return -1;}
    else if (size == 1){ size = 0; }
    else
    {
        arr[0] = arr[--size];
        (this->*pHeapify)(arr, size, 0);
    }
    //Dump(size);
    return 0;
}

template<typename T, uint32_t S, bool bMax /*= true*/>
int32_t PriorityQueue<T, S, bMax>::Push(T &data)
{
    if (size >= S){ return -1; }
    int32_t i = size++;
    arr[i] = data;
    T tmp;
    while (i > 0 && Less(arr[Parent(i)],arr[i]))
    {
        EXCHANGE(arr[Parent(i)], arr[i], tmp);
        i = Parent(i);
    }
    //Dump(size);
    return 0;
}

template<typename T, uint32_t S, bool bMax /*= true*/>
void PriorityQueue<T, S, bMax>::Dump(const uint32_t length /*= S*/)
{
    std::cout << size << ":";
    for (uint32_t i = 0; i < length;++i)
    {
        std::cout << arr[i] << " ";// << std::endl;
    }
    std::cout << std::endl;
}

template<typename T, uint32_t S, bool bMax = false>
T & PriorityQueue<T, S, bMax>::Front()
{
    return arr[0];
}

template<typename T, uint32_t S, bool bMax /*= true*/>
void PriorityQueue<T, S, bMax>::MinHeapify(T arr[], const uint32_t size, const uint32_t i)
{
    uint32_t left = Left(i), right = Right(i), smallest = i;
    if (left < size && arr[left] < arr[i])smallest = left;
    if (right < size && arr[right] < arr[smallest])smallest = right;
    T tmp;
    if (i != smallest)
    {
        EXCHANGE(arr[i], arr[smallest], tmp);
        MinHeapify(arr, size, smallest);
    }
}

template<typename T, uint32_t S, bool bMax /*= true*/>
void PriorityQueue<T, S, bMax>::MaxHeapify(T arr[], const uint32_t size, const uint32_t i)
{
    uint32_t left = Left(i), right = Right(i), largest = i;
    if (left < size && arr[left] > arr[i])largest = left;
    if (right < size && arr[right] > arr[largest])largest = right;
    T tmp;
    if (i != largest)
    {
        EXCHANGE(arr[i], arr[largest], tmp);
        MaxHeapify(arr, size, largest);
    }
}



template<typename T, uint32_t S, bool bMax /*= true*/>
PriorityQueue<T, S, bMax>::~PriorityQueue()
{
    delete[] arr;
    arr = NULL;
}

template<typename T, uint32_t S, bool bMax /*= true*/>
PriorityQueue<T, S, bMax>::PriorityQueue()
{
    arr = new T[S];
    size = 0;
    pHeapify = bMax ? &PriorityQueue::MaxHeapify : &PriorityQueue::MinHeapify;
}

#endif

test file:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>
#include <memory.h>
#include "PriorityQueue.h"

#define MAX_SIZE (100000 + 1)

// 生成不重复的随机数序列写入文件
void gen_test_data(uint32_t cnt)
{
    if (cnt > MAX_SIZE){ printf("cnt too largr
"); return; }
    uint32_t i = 0, m = 0, n = 0;
    int32_t *arr = (int32_t*)malloc(sizeof(int32_t)* cnt);
    while (i < cnt){ arr[i] = i; ++i; }
    char file_name[256];
    sprintf_s(file_name, 256, "test_data_%d.txt", cnt);
    FILE *fp = NULL;
    fopen_s(&fp,file_name, "w");
    if (NULL == fp){ printf("open %s error!
", file_name); return; }
    int32_t tmp = 0;
    i = 0;
    while (i < cnt)
    {
        m = rand() % cnt;
        n = rand() % cnt;
        if (m != n)EXCHANGE(arr[m], arr[n], tmp);
        ++i;
    }
    i = 0;
    while (i < cnt)fprintf(fp, "%d ", arr[i++]);
    fclose(fp);
    printf("gen %s finished
", file_name);
}

// 读取文件
void read_data(int32_t arr[], const int32_t size, int32_t *cnt, const int32_t data_cnt)
{
    FILE *fp = NULL;
    *cnt = 0;
    char file_name[256];
    if (data_cnt > size){ printf("data_cnt too largr
"); return; }
    sprintf_s(file_name, 256, "test_data_%d.txt", data_cnt);
    fopen_s(&fp,file_name, "r");
    if (NULL == fp){ printf("open %s error!
", file_name); return; }
    while (!feof(fp) && *cnt < size)
    {
        fscanf_s(fp, "%d ", &arr[*cnt]);
        (*cnt)++;
    }
    fclose(fp);
}

void dump2(int32_t arr[], const uint32_t start, const uint32_t end)
{
    uint32_t i = start;
    for (; i < end; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("
");
}

int32_t main(int32_t argc, char *argv[])
{
    int32_t cnt = 0;
    const uint32_t data_cnt = 10000;
    int32_t *arr = (int32_t*)malloc(sizeof(int32_t)*data_cnt);
    gen_test_data(data_cnt);
    read_data(arr, MAX_SIZE, &cnt, data_cnt);
    PriorityQueue<int32_t, data_cnt,false> priq;
    // 寻找最小(最大)的K个数
    uint32_t k = 10;
    for (int32_t i = 0; i < cnt; ++i)
    {
        priq.Push(arr[i]);
        if (priq.Size() > k)
        {
            priq.Pop();
        }
    }
    priq.Dump(priq.Size());
    printf("
");
    getchar();
    delete[] arr;
    return 0;
}

测试结果:

gen test_data_10000.txt finished
10:9990 9991 9993 9992 9995 9994 9998 9996 9997 9999