欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之优先队列——二叉堆

程序员文章站 2022-06-05 13:10:22
...


我们之前已经讲过好几种数据结构,其中讲到队列时我们说过队列经常用于打印机作业,此时打印机安排打印作业是按照作业加入打印机的先后顺序进行的。但这未必是最好的做法,例如,现有一项后来插入的特别重要的作业,需要优先打印,此时再按照“先来后到”的原则就不合适了,这种情况在日常生活和工作中十分多见,这时就需要用到今天我们讲的一种十分重要且常用的数据结构——优先队列

简介

优先队列是允许至少两种操作的数据结构:insertinsert(插入)等价于队列中的enqueue(入队),deletedelete(删除)等价于队列中的dequeue(出队)。不过与队列不同,优先队列中的数据不是按照被插入的先后顺序排序的,而是根据某种优先级进行排序(如大小值),这样每次在对优先队列进行删除操作时,就可以保证删除的是队列中的最大或最小值。有很多方法可以实现优先队列,如使用链表,这种实现方法的插入花费高昂而删除花费低廉,适用于删除操作多于插入操作的情形。另一种实现的方法是使用二叉堆,它类似于AVL树,具有结构性和堆序性。下面我们对二叉堆(以下简称堆)的结构性和堆序性进行讲解并进行代码实现。

二叉堆的结构性

堆是一种树状结构,元素在各层中由左到右填入,实际上就是一棵完全二叉树。如下图。
数据结构之优先队列——二叉堆
由我们之前讲到二叉树所总结的可知,高hh的完全二叉树2h2^h2h12^h-1个节点,所以完全二叉树的高是[logN][logN],这个性质非常适合高效率的排序(我们将在后续讲解堆排序),除此之外,因为完全二叉树的规律,我们经常使用数组表示而不用传统的链。见下图。

元素 A B C D E F G H I
下标 0 1 2 3 4 5 6 7 8 9 10

对于数组表示而言,任意位置ii上的元素,其左儿子(若存在)在位置2i2i,其右儿子(若存在)在位置(2i+1)(2i+1),其双亲在[i/2][i/2]。由此可知,采用数组表示时,其遍历操作十分简单。但有一个问题,堆的大小需要提前确定,否则一旦溢出就需要调整大小。

二叉堆的堆序性

堆序性是为了实现其快速查找的要求而产生的。为了快速查找出其最大值或最小值,其最大元素或最小元素应位于根部。并且其任意子树也应符合这个要求。应用此逻辑,在一个堆中,任意节点(根节点除外)xx,其双亲节点中元素应大于(小于)xx中元素。如下图左是一个小顶堆,而右图中6节点不符合小顶堆性质。
数据结构之优先队列——二叉堆

基本性质

insertinsert(插入)和deletedelete(删除)操作是任何堆都需要具有的操作,并且其操作需要实时保持其结构性和堆序性。

insert(插入)

插入元素xx时,我们需要先为堆分配一个节点并将此节点,也就是数组中尾元素的下一个位置。然后我们判断将xx插入这个节点时是否破坏堆序性,若不会则插入完成,否则将此其双亲节点中元素移至此节点中,并将此节点上移至双亲节点,继续判断,重复此过程直至xx可以放置其中。如下图,我们插入14,首先将14放入尾元素下一个位置,破坏其堆序性,将其节点上移至31节点,仍破坏继续上移,直至14放入21节点,插入成功。
数据结构之优先队列——二叉堆
数据结构之优先队列——二叉堆
我们通常将插入元素的操作称为上滤

delete(删除)

删除操作要稍显复杂,删除时堆中元素少了一个,但从数组的角度看我们删除的是数组首元素,删除的数组可用位置确是尾元素位置,所以需要将尾元素上移,因为此时首元素也就是根节点元素被删除了,所以我们首先考虑根节点,若破坏了其堆序性,则将根节点的左右儿子中最小值上移至根节点,其最小儿子置空,继续判断,直至可以将尾元素插入至某一位置。如下图,我们删除堆中最小值,然后将根节点置空,尾元素31不可插入此位置,将根节点左儿子14置空,14上移至根节点,仍不可,继续操作…直至31插入至26节点。
数据结构之优先队列——二叉堆
数据结构之优先队列——二叉堆
数据结构之优先队列——二叉堆
我们将删除操作称为下滤

代码实现

我们在上述的基础上实现一个小顶堆的类,为了解决上述需要提前确定数组容量大小的问题,我们采用容器vectorvector,该类具有公有接口:isEmptyisEmpty(判断是否为空);insertinsert(插入);toptop(返回顶元素);deleteMindeleteMin(删除最小元素);
makeEmptymakeEmpty(清除)。

#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

总结

堆是一种优先队列的实现,采用数组表示方法,可以实现常数时间的查找最小最大值操作。