堆与优先级队列研究(C++)[zz]

堆,是一个很有意思的数据结构。逻辑结构是树,一般为二叉树,每个节点的值都大于(小于)其子树中的任意节点。也就是说,使用堆结构的数组 中,元素 是部分有序的。而正是这个特点,使得在堆上,得到最大值(最小值)的时间复杂度为O(1),移除最大值(最小值)、插入元素、改变元素值(或者是删除位置 已知的元素)的时间复杂度为O(lgn)。另外,用堆结构的排序是一种原地的、时间复杂度为O(nlgn)的排序算法。

可以参见动画演示:演示

在优先级队列前先说一下堆排序。

堆排序和归并排序都是时间复杂度为O(nlgn)的排序算法,不同的是,归并排序不是原地排序,它需要额外的n的空间;而堆排序是在原数组中进行的。

堆排序的过程,首先需要在给定的数组上进行建堆,然后在此基础上一个一个的取根节点放到数组的后部,从后向前排。

建堆的过程BuildHeap代码很简单,从下到上对每个节点依次处理,处理中调用了另一个方法:Heapify,这个才是核心(具体参见完整代码中的私有BuildHeap(void)方法与Heapify(ItemType items[], int index, int count, bool isMaxHeap)方法);Heapify方法对指定节点的子树进行堆化,具体地说,当除了根节点以外,其子树中的所有节点都已经符合堆的要求时,Heapify方 法会把指定的节点的子树调整为一个堆,也就是把指定节点调整到子树中合适的位置上,其时间复杂度为子树的深度,O(lgn)。所以,可以算出建堆的时间复杂度为O(n),是线性的。这个时间复杂度怎么得到的?n长度的树,有lgn层,第h层(从0开始)至多有2^h的节点,进行一下求和就行了。

堆建好了,下来就是排序(具体可以见完整代码中私有的SortTo(ItemType destitionArray[])方法)。因为堆的根节点是最值,所以只需要依次把根节点和堆的最后一个元素交换位置,堆大小-1,再对根节点调用Heapify就可以了。时间复杂度也就是n个Heapify,O(nlgn)。

这样从而得到总的排序时间复杂度O(nlgn)。

优先级队列,目的是从队列中取出的一个元素总是当前队列中的最大值(最小值)。而堆刚好具有这个特点。当然,有序的ArrayList或者LinkedList也是可以的,但是慢,这个后面分析。

看一下优先级队列都需要哪些操作。第一,其根本目的是能取出一个最值元素,这个就不用说了;第二,要能往队列中插入元素。这是两个核心的功能,另带一些其他的辅助功能,如改变其中的某个元素的值,删除某个元素,得到其中的所有元素,得到其中元素个数等等。

给出优先级队列的类的接口:

template

<typename ItemType>

classPriorityQueue {

PriorityQueue(
boolisMaxHeap=true);

PriorityQueue(
intsize,boolisMaxHeap=true);

PriorityQueue(ItemType items[],
intcount,boolisMaxHeap=true);

intCount(void);

ItemType Get();

ItemType Remove();

voidInsert(ItemType value);

voidChange(intindex, ItemType value);

ItemType Remove(
intindex);

boolToArray(ItemType destinationArray[],intdestinationSize);

~PriorityQueue(void);

}


Remove()方法是得到并移除第一个元素,Get()仅仅是返回第一个元素。这个优先级队列用堆实现,从而可以得到主要方法Get()(O(1))、Remove()(O(lgn))、Insert()(O(lgn))较好的性能。具体实现参见完整代码。

Heapify方法书上给的是个递归的,我给改成迭代的了,避免函数调用带来的些许开销,从而可以提高一点内隐的时间与空间的性能。

那么为什么用堆实现优先级队列比较合适呢?有序的线性表呢?

这个不难想,对于线性表,基于数组实现:首先,如果无序,要Get()、要Remove(),肯定要找到个最值,如果每次都去重新搜索,就很慢了,而且数组牵扯到数据的整体移动(O(n));而保持有序,虽然Get()Remove()快,但是Insert(ItemType value)费的功夫有些多,因为堆中只是部分有序,而数组需要保持整体有序,又是数据整体移动(O(n))。

基于链表的呢?链表的修改是很快,但链表如何快速搜索与定位?建索引?-_-!

扯回来,说些关于具体实现时的问题。

当然,Change(int index, ItemType value)Remove(int index)两个方法在实际中是不实用的,或者是不现实的。因为通常情况下,不知道某个元素的index是多少。通常要么就不实现,要么需要搜索,或者有类似索引的机制。

还有,实际使用中队列中存放的元素很可能是个什么东西的指针,而不是一个没什么用的具体数值,这样就还需要进行改进。

一种方式是原有的类不动,用一个实现了比较运算符的类或结构体的包装类包装一个有实际意义的东西,用这个类型当作PriorityQueue的模板参数。

或者是改造PriorityQueue,把模板参数ItemType改成一个结构体或类,思想和上面的相似,不过这样做功能会强大许多。比如添加一个这样的内部类来替代模板参数ItemType
classQueueItem {

public:

QueueItem(ItemType theValue,
intthePriority)

: priority(thePriority), value(theValue) {

}



//Getters and Setters



private:

friend PriorityQueue;

inline
voidSetOnwer(PriorityQueuequeue) {

onwer
=queue;

}

inline
voidSetIndex(intindex) {

this->index=index;

}

inline
intGetIndex() {

returnindex;

}

private:

PriorityQueue
onwer;

intindex;

intpriority;

ItemType value;

};

然后把原先代码中,items改为QueueItem类型的数组;类内部的的ItemType换成QueueItem的指针。QueueItem含有所在PriorityQueueindex,所有的地方注意改动这个;Insert方法中new一个QueueItem来包装ItemType,并返回此类的指针供外部更改使用(构造器就没办法了,可能无法保留带有元素的构造方法);移除的方法中注意回收QueueItem的空间;涉及到index的接口可以改为传入QueueItem的指针,PriorityQueue可直接根据QueueItem指针指向的对象得到index;……细节比较琐碎,不再描述,这个已经超出了本文的范围。

完整的类代码如下:



#include<exception>

#pragmaonce



usingstd::exception;



template

<typename ItemType>

classPriorityQueue {

private:

staticconstintDefaultSize=10;



public:

PriorityQueue(
boolisMaxHeap=true) {

Initialize(nullptr,
0, DefaultSize, isMaxHeap);

}



PriorityQueue(
intsize,boolisMaxHeap=true) {

Initialize(nullptr,
0, size, isMaxHeap);

}



PriorityQueue(ItemType items[],
intcount,boolisMaxHeap=true) {

Initialize(items, count, count, isMaxHeap);

}



//Item count in queue.

inlineintCount(void) {

returncount;

}



//Only get first item.

inline ItemType Get() {

if(count==0) {

//empty queue.

//do something here.

throwexception();

}
else{

returnitems;

}

}



//Get and remove first item.

ItemType Remove() {

if(count==0) {

//empty queue.

//do something here.

throwexception();

}

returnRemove(0);

}



//Add a new item into queue.

voidInsert(ItemType value) {

TryResize(
true);

items[count
-1]=value;

TryMoveUp(count
-1, value);

}



//Change value at index.

voidChange(intindex, ItemType value) {

if(index>=count) {

//out of range.

//throw exception or do nothing.

throwexception();

}



if(isMaxHeap?value<items[index] : value>items[index]) {

TryMoveDown(index, value);

}
elseif(isMaxHeap?value>items[index] : value<items[index]) {

TryMoveUp(index, value);

}
else{

//do nothing.

}

}



ItemType Remove(
intindex) {

if(index>=count) {

//out of range.

//throw exception or do nothing.

throwexception();

}



ItemType result
=items[index];

items[index]
=items[count-1];

TryResize(
false);

if(index!=count-1) {

Heapify(items, index, count, isMaxHeap);

}

returnresult;

}



//Sort all items in queue to destinationArray, destinationSize for safe.

boolToArray(ItemType destinationArray[],intdestinationSize) {

if(destinationSize<count) {

//can not copy all items into destination array.

throwexception();

}



SortTo(destinationArray);

returntrue;

}



~PriorityQueue(void) {

delete [] items;

}



private:

voidInitialize(ItemType items[],intcount,intsize,boolisMaxHeap) {

if(size<count) {

//throw exception or set a new size.

size=count+DefaultSize;

}



this->maxSize=size;

this->count=count;

this->isMaxHeap=isMaxHeap;

this->items=newItemType[size];



if(items!=nullptr) {

for(inti=0; i<count;++i) {

this->items[i]=items[i];

}

BuildHeap();

}

}



voidBuildHeap(void) {

for(inti=ParentIndex(count-1); i>=0;--i) {

Heapify(items, i, count, isMaxHeap);

}

}



//move items[index] down to the right position in its subtree.

voidHeapify(ItemType items[],intindex,intcount,boolisMaxHeap) {



intcurrentIndex=index;

inttargetIndex=index;



if(isMaxHeap) {//... how to do this better?

while(true) {

intleftIndex=LeftChildIndex(currentIndex);

intrightIndex=RightChildIndex(currentIndex);



if(leftIndex<count&&items[leftIndex]>items[targetIndex]) {

targetIndex
=leftIndex;

}

if(rightIndex<count&&items[rightIndex]>items[targetIndex]) {

targetIndex
=rightIndex;

}

if(targetIndex!=currentIndex) {

Swap(items
+targetIndex, items+currentIndex);

currentIndex
=targetIndex;

}
else{

break;

}

}

}
else{

while(true) {

intleftIndex=LeftChildIndex(currentIndex);

intrightIndex=RightChildIndex(currentIndex);



if(leftIndex<count&&items[leftIndex]<items[targetIndex]) {

targetIndex
=leftIndex;

}

if(rightIndex<count&&items[rightIndex]<items[targetIndex]) {

targetIndex
=rightIndex;

}

if(targetIndex!=currentIndex) {

Swap(items
+targetIndex, items+currentIndex);

currentIndex
=targetIndex;

}
else{

break;

}

}

}

}



inline
intLeftChildIndex(intparentIndex) {

returnRightChildIndex(parentIndex)-1;

}

inline
intRightChildIndex(intparentIndex) {

return++parentIndex<<1;

}

inline
intParentIndex(intindex) {

return(++index>>1)-1;

}



voidSortTo(ItemType destitionArray[]) {

//copy items.

for(inti=0; i<count;++i) {

destitionArray[i]
=items[i];

}



//only for exercises... do heap sort in destitionArray.

for(inti=count, tempCount=count; i>0;--i) {

Swap(destitionArray, destitionArray
+tempCount-1);

--tempCount;

Heapify(destitionArray,
0, tempCount, isMaxHeap);

}



}



voidSwap(ItemType
a, ItemTypeb) {

ItemType temp
=
a;

a=b;

b=temp;

}



voidTryMoveUp(intindex, ItemType value) {

if(isMaxHeap?value<items[index] : value>items[index]) {

//do something about value error.

throwexception();

}

items[index]
=value;

intcurrentIndex=index;

intparentIndex=ParentIndex(index);

while(index>0&&(isMaxHeap?items[parentIndex]<items[index] : items[parentIndex]>items[index])) {

Swap(items
+index, items+parentIndex);

index
=parentIndex;

parentIndex
=ParentIndex(parentIndex);

}

}



voidTryMoveDown(intindex, ItemType value) {

if(isMaxHeap?value>items[index] : value<items[index]) {

//do something about value error.

throwexception();

}

items[index]
=value;

Heapify(items, index, count, isMaxHeap);

}



voidTryResize(boolisIncrease) {

if(isIncrease) {

if(count>=maxSize) {

maxSize
=(maxSize<<1)+10;

NewItems(maxSize);

}

++count;

}
else{

if(count<maxSize>>1) {

maxSize
=(maxSize>>1)+5;

NewItems(maxSize);

}

--count;

}

}



voidNewItems(intsize) {

ItemType
newItems=newItemType[size];

//copy items.

for(inti=0; i<count;++i) {

newItems[i]
=items[i];

}

delete [] items;

items
=newItems;

}



private:

ItemType
*items;

intcount;

intmaxSize;

boolisMaxHeap;

};


原文来自:
http://blogold.chinaunix.net/u3/104216/showart_2090365.html

原文链接: https://www.cnblogs.com/avril/archive/2011/05/04/2036918.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/24916

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月8日 上午2:49
下一篇 2023年2月8日 上午2:49

相关推荐