数据结构之优先队列——二叉堆
数据结构之优先队列——二叉堆
我们之前已经讲过好几种数据结构,其中讲到队列时我们说过队列经常用于打印机作业,此时打印机安排打印作业是按照作业加入打印机的先后顺序进行的。但这未必是最好的做法,例如,现有一项后来插入的特别重要的作业,需要优先打印,此时再按照“先来后到”的原则就不合适了,这种情况在日常生活和工作中十分多见,这时就需要用到今天我们讲的一种十分重要且常用的数据结构——优先队列。
简介
优先队列是允许至少两种操作的数据结构:(插入)等价于队列中的enqueue(入队),(删除)等价于队列中的dequeue(出队)。不过与队列不同,优先队列中的数据不是按照被插入的先后顺序排序的,而是根据某种优先级进行排序(如大小值),这样每次在对优先队列进行删除操作时,就可以保证删除的是队列中的最大或最小值。有很多方法可以实现优先队列,如使用链表,这种实现方法的插入花费高昂而删除花费低廉,适用于删除操作多于插入操作的情形。另一种实现的方法是使用二叉堆,它类似于AVL树,具有结构性和堆序性。下面我们对二叉堆(以下简称堆)的结构性和堆序性进行讲解并进行代码实现。
二叉堆的结构性
堆是一种树状结构,元素在各层中由左到右填入,实际上就是一棵完全二叉树。如下图。
由我们之前讲到二叉树所总结的可知,高的完全二叉树到个节点,所以完全二叉树的高是,这个性质非常适合高效率的排序(我们将在后续讲解堆排序),除此之外,因为完全二叉树的规律,我们经常使用数组表示而不用传统的链。见下图。
元素 | A | B | C | D | E | F | G | H | I | ||
---|---|---|---|---|---|---|---|---|---|---|---|
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
对于数组表示而言,任意位置上的元素,其左儿子(若存在)在位置,其右儿子(若存在)在位置,其双亲在上。由此可知,采用数组表示时,其遍历操作十分简单。但有一个问题,堆的大小需要提前确定,否则一旦溢出就需要调整大小。
二叉堆的堆序性
堆序性是为了实现其快速查找的要求而产生的。为了快速查找出其最大值或最小值,其最大元素或最小元素应位于根部。并且其任意子树也应符合这个要求。应用此逻辑,在一个堆中,任意节点(根节点除外),其双亲节点中元素应大于(小于)中元素。如下图左是一个小顶堆,而右图中6节点不符合小顶堆性质。
基本性质
(插入)和(删除)操作是任何堆都需要具有的操作,并且其操作需要实时保持其结构性和堆序性。
insert(插入)
插入元素时,我们需要先为堆分配一个节点并将此节点,也就是数组中尾元素的下一个位置。然后我们判断将插入这个节点时是否破坏堆序性,若不会则插入完成,否则将此其双亲节点中元素移至此节点中,并将此节点上移至双亲节点,继续判断,重复此过程直至可以放置其中。如下图,我们插入14,首先将14放入尾元素下一个位置,破坏其堆序性,将其节点上移至31节点,仍破坏继续上移,直至14放入21节点,插入成功。
我们通常将插入元素的操作称为上滤。
delete(删除)
删除操作要稍显复杂,删除时堆中元素少了一个,但从数组的角度看我们删除的是数组首元素,删除的数组可用位置确是尾元素位置,所以需要将尾元素上移,因为此时首元素也就是根节点元素被删除了,所以我们首先考虑根节点,若破坏了其堆序性,则将根节点的左右儿子中最小值上移至根节点,其最小儿子置空,继续判断,直至可以将尾元素插入至某一位置。如下图,我们删除堆中最小值,然后将根节点置空,尾元素31不可插入此位置,将根节点左儿子14置空,14上移至根节点,仍不可,继续操作…直至31插入至26节点。
我们将删除操作称为下滤。
代码实现
我们在上述的基础上实现一个小顶堆的类,为了解决上述需要提前确定数组容量大小的问题,我们采用容器,该类具有公有接口:(判断是否为空);(插入);(返回顶元素);(删除最小元素);
(清除)。
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#define ERROR 34567890 //一个可能的数,用于错误返回
using namespace std;
template<typename comparable>
class BinaryHeap
{
public:
BinaryHeap() { currentSize = array.size(); };
BinaryHeap(const vector<comparable>& items);
bool isEmpty() const;
void insert(const comparable& x);
comparable top() const;
void deleteMin() ;
void makeEmpty();
private:
int currentSize; //堆中元素个数
vector<comparable> array; //堆的数组
void swap(comparable& x1, comparable& x2);
bool isMinHeap(int position) const;
int down_heap(int position);
};
template<typename comparable>
inline BinaryHeap<comparable>::BinaryHeap(const vector<comparable>& items)
{
currentSize = 0;
if (!items.empty())
{
vector<comparable>::const_iterator iter = items.begin();
for (; iter != items.end(); iter++)
{
insert(*iter);
}
}
}
template<typename comparable>
inline bool BinaryHeap<comparable>::isEmpty() const
{
if (currentSize == 0)
return true;
return false;
}
template<typename comparable>
inline void BinaryHeap<comparable>::insert(const comparable & x)
{
array.push_back(x);
int size = ++currentSize;
if (size == 1)
return;
if (x >= array[size / 2 - 1])
return;
else
{
//size = size / 2;
while ((size / 2) > 0 && array[size - 1] < array[size / 2 - 1])
{
swap(array[size - 1], array[size / 2 - 1]);
size = size / 2;
}
}
}
template<typename comparable>
inline comparable BinaryHeap<comparable>::top() const
{
if (isEmpty())
return ERROR;
return array[0];
}
template<typename comparable>
inline void BinaryHeap<comparable>::deleteMin()
{
if (isEmpty())
return;
else if (currentSize == 1)
{
array.clear();
currentSize = 0;
return;
}
else
{
array[0] = array[currentSize - 1];
array.pop_back();
currentSize--;
int size = 1;
bool is = isMinHeap(size);
while (!isMinHeap(size))
{
size = down_heap(size);
}
}
}
template<typename comparable>
inline void BinaryHeap<comparable>::makeEmpty()
{
currentSize = 0;
array.clear();
}
template<typename comparable>
inline void BinaryHeap<comparable>::swap(comparable& x1, comparable& x2)
{
x1 ^= x2;
x2 ^= x1;
x1 ^= x2;
}
template<typename comparable>
inline bool BinaryHeap<comparable>::isMinHeap(int position) const
{
if (currentSize >= position * 2 + 1)
{
if (array[position - 1] > array[position * 2 - 1] <= array[position * 2] ? array[position * 2 - 1] : array[position * 2])
return false;
return true;
}
else if (currentSize >= position * 2)
{
if (array[position - 1] > array[position * 2 - 1])
return false;
return true;
}
else
return true;
}
template<typename comparable>
inline int BinaryHeap<comparable>::down_heap(int position)
{
if (currentSize >= position * 2 + 1)
{
int size = array[position * 2 - 1] <= array[position * 2] ? position * 2 : position * 2 + 1;
swap(array[position - 1], array[position * 2 - 1] <= array[position * 2] ? array[position * 2 - 1] : array[position * 2]);
return size;
}
else
{
swap(array[position - 1], array[position * 2 - 1]);
return position * 2;
}
}
测试:
#pragma once
#include "BinaryHeap.h"
#include <iostream>
using namespace std;
int main()
{
vector<int> vec = { 3,5,8,4,9 };
BinaryHeap<int> heap(vec);
cout << heap.top() <<endl;
heap.insert(2);
cout << heap.top() << endl;
heap.deleteMin();
cout << heap.top() << endl;
getchar();
}
输出:
3
2
3
总结
堆是一种优先队列的实现,采用数组表示方法,可以实现常数时间的查找最小最大值操作。
上一篇: 《控制》可吃掉18.5GB显存:唯有Titan RTX可满足
下一篇: 毛肚怎么处理干净无异味