优先级队列（Priority Queue）是一种广泛使用的数据结构。其内部元素按照设定的关键字大小（亦可称为优先级别）出队。

使用原始的队列来实现优先级队列，虽然入队效率可以达到Θ(1)，但是出队需要对整个队列进行遍历，复杂度需要Θ(N)。

因而优先级队列一般不采用原始队列实现，转而使用堆结构(heap)，尤其是最小堆实现。

关于堆数据结构，请参考http://blog.kingsamchen.com/archives/547以及http://en.wikipedia.org/wiki/Heap_%28data_structure%29

基本操作

元素的插入-Insert

和堆排序不同，优先级队列是一个容器，元素需要依次插入。

插入算法比较简单：先将元素插入到下一个可用空间。此时在堆结构中，对应为一个叶子结点。由于元素的插入可能破坏堆特性，即：插入的元素key小于其父结点。此时从结点处向上调整，过程称为PercolateUp，上滤。

PercolateUp操作停止的断言为：{到达根结点 || 已符合堆结构}。

另外，如果堆内部数组从下标1开始存放数据，除了使得PARENT/LEFTCHILD/RIGHTCHILD的公式更简洁之外，还可以往首元素填入一个哨兵元素（元素值永远最小）用以简化PercolateUp操作，避免对是否到达根结点进行判断。

Insert操作的复杂度是O(logN)，这是最坏情况，但是实际应用中情形往往稍好。

元素获取-ExtractMin

首先，最小堆性质保证了根结点元素具有最大的优先级，所以我们只需要返回根结点的一个copy，并且删除根结点。

但是直接删除根结点会破坏整个堆，而且删起来也蛋疼（想想，的确够蛋疼的）。所以通常会用最后一个叶子的元素去取代根结点，以保持整个堆看起来还存在。

但是这种取代十有八九会破坏堆性质（除非叶子结点优先级和原先根结点相同），所以需要从根结点出向下调整，过程成为PercolateDown，下滤。

PercolateDown基本上都会将元素重新调整到最底层，所以需要临界条件的判断。

另外，PercolateDown和PercolateUp稍有不同：每一次向下一层递进，都一定要确保上浮的元素是几个元素中最小的。而这又会引发另外一个问题，父结点可能有一个孩子，可能有两个孩子。

所以Percolate实现相对较麻烦，而且也难以用哨兵。

ExtractMin的复杂度是O(logN)，而且由于下滤的特殊性，一般都会达到这个上界

扩展操作

元素查找-Find

对一种数据结构来说，查找要求是经常会发生的。比如在进程表中查找某个进程。

但是堆不像BinarySearch，并没有表现出太强的顺序性，所以查找通常之能遍历整个堆。复杂度为Θ(N)
Read the rest of this entry »

一、概述

树是一种重要的数据结构，而二叉树则是树中重要的一类

二叉树是特殊的树，最明显的特点在于，每个结点都有左子结点和右子结点，且二者有序不能随意互换。

二叉树有两种特殊形式：满二叉树和完全二叉树，而且都具有一定的性质，具体参照偶之前写过《堆和堆排序》的文章

二叉树的重点是结点，通常存在二叉链接和三叉链接两种结点，区别在于三叉链接多了一个指向父结点的指针，因而三叉链接结点在遍历时比二叉具有优势。二叉与三叉结点适用于不同的场合和需求。

如无特殊说明，本文采用的是二叉结点

二、二叉树的建立

在堆中，我们利用数组来构建二叉树（完全二叉树）。但是如果用数组来表示一般的二叉树，则会造成内存空间的极度浪费。

所以，通常情况下，我们通过链表来建立二叉树。

和遍历类似，建立二叉树也有不同的方法，其建立的结果自然也有所不同。用的比较多的有“按顺序建立二叉树”、“从已有数据建立完全二叉树”等等。但是无论哪种方法，本质都需要通过递归实现。

本文的范例采用的是建立完全二叉树，因而需要了解一些与完全二叉树有关的数学性质

template<typename T>
struct TreeNode
{
	T Data;
	TreeNode<T>* pLeftNode;
	TreeNode<T>* pRightNode;
};

template<typename T>
CBinTree<T>::CBinTree(const T ary[], int nCount)
{
	CreateBinTree(m_pRoot, ary, 0, nCount - 1);
}

template<typename T>
void CBinTree<T>::CreateBinTree(TreeNode<T>*& pNode, const T ary[], int i, int nIdxMax)
{
	pNode = new TreeNode<T>;
	_ASSERT(m_pRoot != NULL);

	// zero-based
	int nLeftIdx = (i << 1) + 1;
	int nRightIdx = (i + 1) << 1;

	pNode->Data = ary[i];

	// if leftchild is empty, rightchild is empty too
	if (nLeftIdx <= nIdxMax)
	{
		CreateBinTree(pNode->pLeftNode, ary, nLeftIdx, nIdxMax);

		if (nRightIdx <= nIdxMax)
		{
			CreateBinTree(pNode->pRightNode, ary, nRightIdx, nIdxMax);
		}
		else
		{
			pNode->pRightNode = NULL;
		}
	}
	else
	{
		pNode->pLeftNode = NULL;
		pNode->pRightNode = NULL;
	}
}

三、二叉树的遍历

二叉树的遍历方法有多种，最常用的有中序遍历、先序遍历和后序遍历。毫无例外，这三种遍历方法都是基于递归/迭代的思想

为了更好的说明三种遍历，结合图片。
Read the rest of this entry »

1.什么是堆

这里的堆（二叉堆），指得不是堆栈的那个堆，而是一种数据结构。

堆可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

如下图，是一个堆和数组的相互关系

二叉堆一般分为两种：最大堆和最小堆。两种堆内部的数据都要满足自己的特点。

比如最大堆的特点是，每个父节点的元素值都不小于其孩子结点（如果存在）的元素值，因此，最大堆的最大元素值出现在根结点（堆顶）

最小堆的性质与最大堆恰好相反

由于堆排序算法使用的是最大堆，所以我们这里以最大堆为例，最小堆情况类似，可以自己推导

对于给定的某个结点的下标i，可以很容易的计算出这个结点的父结点、孩子结点的下标，而且计算公式很漂亮很简约

但是这里有一个很大的问题：目前主流的编程语言中，数组都是Zero-based，这就意味着我们的堆数据结构模型要发生改变
Read the rest of this entry »