堆,是一个很有意思的数据结构。逻辑结构是树,一般为二叉树,每个节点的值都大于(小于)其子树中的任意节点。也就是说,使用堆结构的数组中,元素
是部分有序的。而正是这个特点,使得在堆上,得到最大值(最小值)的时间复杂度为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>
- class
PriorityQueue {
- PriorityQueue(bool
isMaxHeap =
true
);
- PriorityQueue(int
size,
bool
isMaxHeap =
true
);
- PriorityQueue(ItemType items[], int
count,
bool
isMaxHeap =
true
);
- int
Count(
void
);
- ItemType Get();
- ItemType Remove();
- void
Insert(ItemType value);
- void
Change(
int
index, ItemType value);
- ItemType Remove(int
index);
- bool
ToArray(ItemType destinationArray[],
int
destinationSize);
- ~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
:
- class
QueueItem {
- public
:
- QueueItem(ItemType theValue, int
thePriority)
- : priority(thePriority), value(theValue) {
- }
-
-
-
- private
:
- friend PriorityQueue;
- inline void
SetOnwer(PriorityQueue* queue) {
- onwer = queue;
- }
- inline void
SetIndex(
int
index) {
- this
->index = index;
- }
- inline int
GetIndex() {
- return
index;
- }
- private
:
- PriorityQueue* onwer;
- int
index;
- int
priority;
- ItemType value;
- };
然后把原先代码中,items
改为QueueItem
类型的数组;类内部的的ItemType
换成QueueItem
的指针。QueueItem
含有所在PriorityQueue
的index
,所有的地方注意改动这个;Insert
方法中new
一个QueueItem
来包装ItemType
,并返回此类的指针供外部更改使用(构造器就没办法了,可能无法保留带有元素的构造方法);移除的方法中注意回收QueueItem
的空间;涉及到index
的接口可以改为传入QueueItem
的指针,PriorityQueue
可直接根据QueueItem
指针指向的对象得到index;……
细节比较琐碎,不再描述,这个已经超出了本文的范围。
完整的类代码如下:
- #include
- #pragma once
-
- using
std::exception;
-
- template
- <typename
ItemType>
- class
PriorityQueue {
- private
:
- static
const
int
DefaultSize = 10;
-
- public
:
- PriorityQueue(bool
isMaxHeap =
true
) {
- Initialize(nullptr, 0, DefaultSize, isMaxHeap);
- }
-
- PriorityQueue(int
size,
bool
isMaxHeap =
true
) {
- Initialize(nullptr, 0, size, isMaxHeap);
- }
-
- PriorityQueue(ItemType items[], int
count,
bool
isMaxHeap =
true
) {
- Initialize(items, count, count, isMaxHeap);
- }
-
-
- inline
int
Count(
void
) {
- return
count;
- }
-
-
- inline
ItemType Get() {
- if
(count == 0) {
-
-
- throw
exception();
- } else
{
- return
*items;
- }
- }
-
-
- ItemType Remove() {
- if
(count == 0) {
-
-
- throw
exception();
- }
- return
Remove(0);
- }
-
-
- void
Insert(ItemType value) {
- TryResize(true
);
- items[count - 1] = value;
- TryMoveUp(count - 1, value);
- }
-
-
- void
Change(
int
index, ItemType value) {
- if
(index >= count) {
-
-
- throw
exception();
- }
-
- if
(isMaxHeap ? value < items[index] : value > items[index]) {
- TryMoveDown(index, value);
- } else
if
(isMaxHeap ? value > items[index] : value < items[index]) {
- TryMoveUp(index, value);
- } else
{
-
- }
- }
-
- ItemType Remove(int
index) {
- if
(index >= count) {
-
-
- throw
exception();
- }
-
- ItemType result = items[index];
- items[index] = items[count - 1];
- TryResize(false
);
- if
(index != count - 1) {
- Heapify(items, index, count, isMaxHeap);
- }
- return
result;
- }
-
-
- bool
ToArray(ItemType destinationArray[],
int
destinationSize) {
- if
(destinationSize < count) {
-
- throw
exception();
- }
-
- SortTo(destinationArray);
- return
true
;
- }
-
- ~PriorityQueue(void
) {
- delete
[] items;
- }
-
- private
:
- void
Initialize(ItemType items[],
int
count,
int
size,
bool
isMaxHeap) {
- if
(size < count) {
-
- size = count + DefaultSize;
- }
-
- this
->maxSize = size;
- this
->count = count;
- this
->isMaxHeap = isMaxHeap;
- this
->items =
new
ItemType[size];
-
- if
(items != nullptr) {
- for
(
int
i = 0; i < count; ++i) {
- this
->items[i] = items[i];
- }
- BuildHeap();
- }
- }
-
- void
BuildHeap(
void
) {
- for
(
int
i = ParentIndex(count - 1); i >= 0; --i) {
- Heapify(items, i, count, isMaxHeap);
- }
- }
-
-
- void
Heapify(ItemType items[],
int
index,
int
count,
bool
isMaxHeap) {
-
- int
currentIndex = index;
- int
targetIndex = index;
-
- if
(isMaxHeap) {
- while
(
true
) {
- int
leftIndex = LeftChildIndex(currentIndex);
- int
rightIndex = 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
) {
- int
leftIndex = LeftChildIndex(currentIndex);
- int
rightIndex = 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
int
LeftChildIndex(
int
parentIndex) {
- return
RightChildIndex(parentIndex) - 1;
- }
- inline
int
RightChildIndex(
int
parentIndex) {
- return
++parentIndex << 1;
- }
- inline
int
ParentIndex(
int
index) {
- return
(++index >> 1) - 1;
- }
-
- void
SortTo(ItemType destitionArray[]) {
-
- for
(
int
i = 0; i < count; ++i) {
- destitionArray[i] = items[i];
- }
-
-
- for
(
int
i = count, tempCount = count; i > 0; --i) {
- Swap(destitionArray, destitionArray + tempCount - 1);
- --tempCount;
- Heapify(destitionArray, 0, tempCount, isMaxHeap);
- }
-
- }
-
- void
Swap(ItemType* a, ItemType* b) {
- ItemType temp = *a;
- *a = *b;
- *b = temp;
- }
-
- void
TryMoveUp(
int
index, ItemType value) {
- if
(isMaxHeap ? value < items[index] : value > items[index]) {
-
- throw
exception();
- }
- items[index] = value;
- int
currentIndex = index;
- int
parentIndex = ParentIndex(index);
- while
(index > 0 && (isMaxHeap ? items[parentIndex] < items[index] : items[parentIndex] > items[index])) {
- Swap(items + index, items + parentIndex);
- index = parentIndex;
- parentIndex = ParentIndex(parentIndex);
- }
- }
-
- void
TryMoveDown(
int
index, ItemType value) {
- if
(isMaxHeap ? value > items[index] : value < items[index]) {
-
- throw
exception();
- }
- items[index] = value;
- Heapify(items, index, count, isMaxHeap);
- }
-
- void
TryResize(
bool
isIncrease) {
- if
(isIncrease) {
- if
(count >= maxSize) {
- maxSize = (maxSize << 1) + 10;
- NewItems(maxSize);
- }
- ++count;
- } else
{
- if
(count < maxSize >> 1) {
- maxSize = (maxSize >> 1) + 5;
- NewItems(maxSize);
- }
- --count;
- }
- }
-
- void
NewItems(
int
size) {
- ItemType* newItems = new
ItemType[size];
-
- for
(
int
i = 0; i < count; ++i) {
- newItems[i] = items[i];
- }
- delete
[] items;
- items = newItems;
- }
-
- private
:
- ItemType* items;
- int
count;
- int
maxSize;
- bool
isMaxHeap;
- };
阅读(1725) | 评论(0) | 转发(0) |