使用模版实现的基于二叉堆的优先级队列(原)

使用模版实现的基于二叉堆的优先级队列

这里实现的是小顶堆

     主要的功能:

    Type & PopHeap();//弹出一个最小元素

        //将最小的元素和最后一个元素进行交换，将移走最小元素的剩余元素组成的序列再转换成一个小顶堆。并将最小元素返回。

    void PushHeap(const Type & elem); //插入一个元素,将插入元素后的序列调整成小顶堆

   //将插入的元素放置在数组的最后一个位置，经过一次调整(不用进行递归调整)，即沿一条树枝向上调整，形成新的小顶堆

    bool EditItem(Type & pItem);

相关代码如下:
注意这个代码有一个问题就是这个只适用于再该优先级队列中存放相关类型的指针！而不适用于存放相关的对象，因为在比较的时候使用了接引操作符，其实去了相应的接引操作符，就适合一般的情况了，只是这种情况下在该优先级队列中存放相应的指针，需要自己实现这个函数
bool operator==(const ClassName * p1，const ClassName * p2);

#pragma once

#include "stdafx.h"

template class CPriorityQueue

{

public:

       enum{BRANCH = 2};

       CPriorityQueue();

       ~CPriorityQueue(void);

 private:

       Type * data;    //指向第一条数据的指针

       size_t maxSize;      //最大的容量

       size_t cur;   //现存元素的个数

 

public:

       bool isEmpty(){return cur==0;}

       void Clear(){cur = 0;}

       Type & PopHeap();

       void PushHeap(const Type & elem);

       bool EditItem(Type & pItem);

private:

       int Parent(int i) { return i / BRANCH; }

       int Left(int i)   { return i * BRANCH; }

       int Right(int i)  { return i * BRANCH + 1; }

       int Update(int i);

       void Adjustify(int i);

};

 

template CPriorityQueue::CPriorityQueue()

{

       maxSize = 1023;

       this->data = new Type[maxSize+1];

       this->cur = 0;

}

 

template CPriorityQueue::~CPriorityQueue()

{

       //注意这里只进行清空，不进行删除相应的元素，删除由其他部分负责

       this->cur = 0;

       if(this->data)

       {

              this->data = NULL;

       }

}

 

template void CPriorityQueue::PushHeap(const Type & elem)

{

       //将插入的元素放置在数组的最后一个位置，经过一次调整(不用进行递归调整)，即沿一条树枝向上调整，形成新的小顶堆

       cur = cur + 1;

       if(cur == maxSize)

       {

              maxSize <<= 1;

              Type * pTempData = new Type[maxSize];

              memcpy(pTempData,data,sizeof(void * ) * cur);

              //delete []data;//注意这里不能使用Delete,因为存放的有可能是指针

              data = NULL;

              data = pTempData;

       }

       int key = cur;

       int i;

       data[key] = elem;

       i = Parent(key);

       while(i>0)

       {

              if((*data[i]) > (*elem))

              {

                     //swap i,key

                     data[0] = data[i];

                     data[i] = elem;

                     data[key] = data[0];

                     key = i;

                     i = Parent(i);

              }

              else break;

       }

}

 

template Type & CPriorityQueue::PopHeap()

{    

       //将最小的元素和最后一个元素进行交换，将移走最小元素的剩余元素组成的序列再转换成一个小顶堆

       //从上向下依次进行调整，建立以i节点为根节点的小顶堆

       Type min =  data[1];

       data[1] = data[cur];

       cur--;

       Adjustify(1);

       return min;

}

 

template void CPriorityQueue::Adjustify(int i)

{

       //建立以i节点为根节点的小顶堆，注意这里要进行递归调用,因为每一次调整，都会影响下面的小顶堆结构

       int left = Left(i);

       int right = Right(i);

       int smallest = i;

       if (left <= cur && (*data[smallest]) > (*data[left]))

              smallest = left;

 

       if (right <= cur && (*data[smallest]) > (*data[right]))

              smallest = right;

 

       if (smallest != i)

       {

              //swap(data[smallest], data[i]);

              data[0] = data[smallest];

              data[smallest] = data[i];

              data[i] = data[0];

              Adjustify(smallest);

       }

}

 

template bool CPriorityQueue::EditItem(Type & pItem)

{

       if(pItem == NULL)

              _ASSERT(FALSE);

       data[0] = pItem;

       size_t i  = cur;

       for(; (*data[i]) != (*pItem); i--);

       if(i == 0)

       {

              //没有找到这个结点那么就把这个结点当作新的元素加进来

              PushHeap(pItem);

              _ASSERT(FALSE);

       }

       else

       {

              //找到这个元素,修改它的值

              Update(i);

       }

       return true;

}

 

template int CPriorityQueue::Update(int i)

{

       data[0] = data[i];

       int parentNode = Parent(i);

       if(parentNode == 0)

       {

              return 0;

       }

       while((*data[parentNode]) > (*data[i]))

       {

              data[i] = data[parentNode];

              data[parentNode] = data[0];

              i = parentNode;

              parentNode = Parent(i);

       }

       return i;

}