KJHの博客

记录&回忆

0%

数据结构的二叉堆(堆)

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟

二叉堆（也叫堆）是一个部分排序的二叉树，其排序规则体现在它的堆序性质上：最大堆和最小堆，最大堆就是其对于任一节点，每个节点的键值都大于等于它的孩子节点，所以根节点键值最大。最小堆则相反。

堆是一棵完全二叉树，具备完全二叉树的性质，可以用一个数组表示而不需要指针，在起始位置为 0 的数组中任一位置 i 上的元素，其左儿子在位置 2*1+1 上，右儿子在左儿子的后面邻近位置上，它的父节点则在位置 (i-1)/2。因此，一个堆数据结构将由一个数组（不管键值是什么类型）、一个代表最大容量的整数以及当前的堆大小组成。

下面用C++ 来实现堆，并补充基于堆这一数据结构上的堆排序，不同于前面介绍的堆排序

  1. 堆的类结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <class Elem>
class BinaryHeap
{
public:
	BinaryHeap(int MaxSize = 50);
	BinaryHeap(const BinaryHeap<Elem> &rhs);
	BinaryHeap(Elem *Array, int ElemNum, int MaxSize);
	~BinaryHeap(void);

	Elem *Sort(void);              //堆排序
	bool Add(const Elem &Item);    //添加元素
	Elem Remove(void);             //移除（堆顶）元素
	 
	inline int GetSize(void);      //获取当前堆大小

protected:
	Elem *Data;                    
	int CurrentNum;
	const int MAX_SIZE;

	void HeapifyUp(int Node);            //向上调整堆  
	void HeapifyDown(int Node);          //向下调整堆
	 
	inline int ParentOf(int Node);       //得到节点的父节点位置
	inline int LeftChildOf(int Node);    //得到节点的左儿子位置

};
  1. 构造函数，拷贝构造函数，析构函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//constructor function
template <class Elem>
BinaryHeap<Elem>::BinaryHeap(int MaxSize) :MAX_SIZE(MaxSize)
{
	Data = new Elem[MAX_SIZE];
	CurrentNum = 0;
}

//copy constructor function
template <class Elem>
BinaryHeap<Elem>::BinaryHeap(const BinaryHeap<Elem> &rhs) :MAX_SIZE(rhs.MAX_SIZE), CurrentNum(rhs.CurrentNum)
{
	Data = new Elem[MAX_SIZE];
	strcpy(Data, rhs.Data);
}

//array constructor
//将数组元素构建成最大堆
template <class Elem>
BinaryHeap<Elem>::BinaryHeap(Elem *Array, int ElemNum, int MaxSize) :MAX_SIZE(MaxSize)
{
	Data = new Elem[MAX_SIZE];
	CurrentNum = ElemNum;

	for (int i = 0; i < ElemNum; ++i)
		Data[i] = Array[i];
	 
	for (int i = ParentOf(CurrentNum - 1); i >= 0; --i)   //单步向前，数组从后往前，树从上到下调整
		HeapifyDown(i);

}

template <class Elem>
BinaryHeap<Elem>::~BinaryHeap(void)
{
	if (Data)
		delete[] Data;
}
  1. 最大堆调整（最小堆只需修改比较即可）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <class Elem>
int BinaryHeap<Elem>::ParentOf(int Node)
{
	//assert(Node > 0);
	return (Node - 1) / 2;
}

template <class Elem>
int BinaryHeap<Elem>::LeftChildOf(int Node)
{
	return (Node * 2) + 1;
}

//最大堆调整：从Node位置向上调整（数组向前，Node后不管）
template <class Elem>
void BinaryHeap<Elem>::HeapifyUp(int Node)
{
	int Current = Node;
	int Parent = ParentOf(Node);
	Elem Item = Data[Current];

	while (Current > 0)
	{
		if (Item > Data[Parent])
		{
			Data[Current] = Data[Parent];
			Current = Parent;
			Parent = ParentOf(Current);
		}
		else
			break;
	}
	Data[Current] = Item;

}

//最大堆调整：从Node位置向下调整（数组向后，Node前不管）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <class Elem>
void BinaryHeap<Elem>::HeapifyDown(int Node)
{
	int Current = Node;
	int Child = LeftChildOf(Node);
	Elem Item = Data[Current];

	while (Child < CurrentNum)
	{
		if (Child < (CurrentNum - 1))
		{
			if (Data[Child] < Data[Child + 1])
				++Child;
		}
	 
		if (Item < Data[Child])
		{
			Data[Current] = Data[Child];
			Current = Child;
			Child = LeftChildOf(Current);
		}
		else
			break;
	}
	Data[Current] = Item;

}

此处给出最大堆向上调整 HeapifyUp 演示：Node = ParentOf(CurrentNum - 1)；

此处给出最大堆向上调整 HeapifyUp 演示：Node = ParentOf(CurrentNum - 1)；

那什么时候向上调整，什么时候向下调整呢？很明显构建二叉堆的时候必须向上迭代（递归）调整，另外添加元素也必须向上调整；而移除堆顶元素（排序）后，则需要从上向下调整。也就是说当原数组不是二叉堆或是往后面添加元素打乱稳定时，需要从下往上调整；移除元素后，虽然数组不是二叉堆形式了，但是有一子树是不需移动的，只需调整另外一边子树。通俗点就是抽走前面的需要向下调整，后面添加需要向前调整。

  1. 添加、移除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template <class Elem>
bool BinaryHeap<Elem>::Add(const Elem &Item)
{
	if (CurrentNum >= MAX_SIZE)
		return false;

	Data[CurrentNum] = Item;
	HeapifyUp(CurrentNum++);
	return true;

}

template <class Elem>
Elem BinaryHeap<Elem>::Remove(void)
{
	assert(CurrentNum > 0);

	Elem Temp = Data[0];
	Data[0] = Data[--CurrentNum];  //此处是用数组最后一个填补
	HeapifyDown(0);                //从上往下调整
	return Temp;
	 
	//或选择键值大的儿子填补空位，重复该步骤直到最后一个元素填补了空位 	

}

  1. 堆排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    5. template <class Elem>
       inline int BinaryHeap<Elem>::GetSize(void)
       {
       return CurrentNum;
       }

    template <class Elem>
    Elem* BinaryHeap<Elem>::Sort(void)
    {
    	Elem *NewArray = new Elem[CurrentNum];

    	//升序
    	for (int ElemNum = CurrentNum - 1; ElemNum >= 0; --ElemNum)
    		NewArray[ElemNum] = Remove();
    	 
    	/*降序
    	int ElemNum = CurrentNum;
    	for (int i = 0; i < ElemNum; ++i)
    		NewArray[i] = Remove();
    	*/
    	 
    	return NewArray;

    }