二叉堆-堆排序

堆是实现优先级队列效率很高的数据结构,如C++STL priority_queue、Python PriorityQueue。堆的变体很多,二叉堆、斐波那契堆…由堆实现的一种高效排序算法为堆排序。

二叉堆

注意:数据结构中的堆和内存中的堆是两个完全不同的概念,就像数据结构栈和栈内存一样,之间没有必然联系。
堆(Heap)也可称为大/小根堆、大/小根树,最大/小堆:

  • 其中每个节点的值大于等于或小于等于其子节点(如果存在)的值;
  • 一个大根堆(小根堆)是完全二叉树

二叉堆由J.W.J.Williams于1964年引入,作为堆排序的数据结构。
一般来说,默认指的是二叉堆(Binary heap)
由于堆是完全二叉树,因此我们可以用数组描述,也可以用链表描述,不过数组描述比较普遍。

二叉堆中某个节点的左右子节点无论谁大谁小,只要满足子节点的值小于其父节点的值(最大堆)或大于其父节点的值(最小堆)即可。

由于用数组描述的二叉堆,堆节点存储在数组中,那么如何用数组表示呢?节点的父子关系又如何解决?
1.因为二叉堆是完全二叉树,所以从上到下,从左到右依次将二叉堆节点填入数组,数组之间没有空隙。
2.这里有两种映射方式。假设父节点索引为 ii,左孩子节点索引为 ll,右孩子节点索引为 rr,则:
数组索引从0开始:

l=2i+1l=2i+1r=2i+2r=2i+2i=l12=r12i=\lfloor \frac{l-1}{2} \rfloor=\lfloor \frac{r-1}{2} \rfloor

数组索引从1开始:

l=2il=2ir=2i+1r=2i+1i=l2=r2i=\lfloor \frac{l}{2} \rfloor=\lfloor \frac{r}{2} \rfloor

两者均采用了向下取整floor是防止数组下标越界同时还能保证不同左右孩子的父节点索引相同;数组索引从1开始是为了简化运算,除此之外没有差别,本文是采用第一种方式。

本文仅仅演示最大堆的基本操作,最小堆也是类似的。
首先定义堆的ADT

1
2
3
4
5
6
7
8
9
10
template<class T>
class Heap{
public:
virtual void push(const T&)=0;
virtual int size()=0;
virtual T& top()=0;
virtual void pop()=0;
virtual bool empty()=0;
virtual ~Heap(){}
};

Heap派生出最大堆maxHeap

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
template<class T>
class maxHeap: public Heap<T>{
public:
maxHeap(int init_capacity=20);
~maxHeap();
// 插入元素
void push(const T& data);
// 删除堆顶元素
void pop();
int size(){return m_heapSize;}
int capacity(){return m_capacity;}
// 获取堆顶元素
T& top(){
if(m_heapSize>=1)
return m_heap[0];
throw "heap is empty";
};
bool empty(){return m_heapSize==0;}
protected:
// 改变数组大小
void changeHeapCapacity(int oldLength,int newLength){
T *temp=new T[newLength];
m_capacity=newLength;
std::copy(m_heap,m_heap+m_heapSize,temp);
delete[] m_heap;
m_heap=temp;
}
private:
T *m_heap;
int m_capacity;
int m_heapSize;
};
二叉堆的插入

最大堆的插入必须要确保每个节点\ge其子节点。
向最大堆插入一个节点步骤如下:

  • 在最大堆的底部最左边添加一个新节点作为子节点,也就是在数组内有效元素的下一个位置插入;
  • 若子节点>父节点,则交换它们的值,继续向上调整;否则调整结束。

二叉堆插入时间复杂度为O(Height)=O(logn)O(Height)=O(\log n)

向上调整就像冒泡排序一样,从叶子到根不断将新节点移动到某个位置直到该新节点\le其父节点。
以下图为例,假设数组大小为12,在数组尾部插入70后是不满足二叉堆性质的,因此需要调整。调整方法很简单,依次将70“上浮”到某个合适的位置,也就是通过比较该节点与父节点的值来进行的。

由于70>45,节点70在数组中的索引为8,可以计算出父节点45索引为812=3\lfloor \frac{8-1}{2} \rfloor=3,于是交换他们的值,此时节点70所在数组的索引为3;

接着继续判断节点70父节点60大小,70>60,继续交换节点70父节点60的值;此时70<80,调整结束。

如果在空堆中插入节点直接插入即可,注意此处并没有直接交换父节点和子节点,而是将父节点不断的向下移动,最后在合适位置插入新节点。

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 T>
void maxHeap<T>::push(const T&data){
// 数组扩容
if(m_heapSize>=m_capacity){
changeHeapCapacity(m_capacity,2*m_capacity);
}
// 子节点索引
int index=m_heapSize;
// 父节点索引,向下取整
int parent_index=((index-1)/2);

// 向上调整
while (true) {
if(index==0)break;
// 若子节点大于父节点,继续向上调整
if(data > m_heap[parent_index])
m_heap[index]=m_heap[parent_index];
else
break;
index=parent_index;
parent_index=((index-1)/2);
}
m_heap[index]=data;
m_heapSize++;
}
二叉堆的删除

一般二叉堆的删除指的是删除堆顶元素,其步骤如下:

  • 删除堆顶元素并将二叉堆最底层的最后一个节点(数组最后一个元素)替换到堆顶位置(数组第一个元素);
  • 先比较父节点的左右孩子的大小,较大的子节点再与父节点进行比较,若父节点<其子节点,继续向下调整;否则调整结束。

二叉堆删除时间复杂度为O(Height)=O(logn)O(Height)=O(\log n)


删除根节点80,将节点45替换到根节点,此时不满足二叉堆性质,故继续向下调整。此时有效数组大小为heapSize-1

  • 父节点45的左右孩子节点70>50且45<70,故交换值后继续向下调整;
  • 父节点45的左右孩子节点60>40且45<60,故交换值后继续向下调整;
  • 父节点45只有左孩子且45>10,故调整结束。

类似插入操作此处也并没有直接交换父节点和子节点值,而是将子节点不断的向上移动,最后在合适位置插入旧值。

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
template<class T>
void maxHeap<T>::pop(){
if(m_heapSize<=0)
return;
int index=0;
int child_index=2*index+1;
int lastChild=m_heap[--m_heapSize];

// 向下调整
while (true){
if(child_index >= m_heapSize)
break;
// 当父节点只有一个左孩子时,child_index+1 < m_heapSize不成立
if(child_index+1 < m_heapSize && m_heap[child_index]<m_heap[child_index+1]){
child_index++;
}
// 若父节点<子节点,继续向下调整
if(lastChild < m_heap[child_index])
m_heap[index]=m_heap[child_index];
else
break;
index=child_index;
child_index=2*index+1;
}
m_heap[index]=lastChild;
}
构建二叉堆

构建二叉堆是在一个循环内不断地插入元素,实际上这是Williams法,其复杂度为O(nlogn)O(n\log n)

1
2
3
4
5
int array[]={90 , 40 ,30 ,60 ,70 ,200 ,20 ,10 ,50 ,80};
maxHeap<int>mhp;
for(auto &&x:array) {
mhp.push(x);
}

但是,Williams的方法不够好。事实上,我们可以直接在原数组通过向下调整的方法来建堆,而且这种方法比上面的方法还要快。
维基百科中有一段话

More specifically if all the subtrees starting at some height hh have already been “heapified” (the bottommost level corresponding to h=0h=0), the trees at height h+1h+1 can be heapified by sending their root down along the path of maximum valued children when building a max-heap, or minimum valued children when building a min-heap

大概意思是说,如果一个二叉堆的底层子树也是二叉堆的话,那么可以逐层向上合并这些子二叉堆,也就是在hh层存在多个子树已经堆化,那么在h+1h+1层可以很快的完成调整。

1
2
3
4
Build-Max-Heap (A):
heap_length[A] ← length[A]
for each index i from floor((length[A]-1-1)/2) downto 0 do:
Max-Heapify(A, i)

比如下面这张图,数组表示为[90 40 30 60 70 200],这不是一个二叉堆,现在需要将其调整为二叉堆。
floor((length[A]-1-1)/2)开始(最后一个子节点的父节点),依次递减直到0(根节点),虚线框表示已经完成堆化的子树。

其中parent代表要下浮的节点,从父节点开始将parent下浮到某个合适位置。最后结果就是真正的二叉堆[200 70 90 60 40 30]

总之该方法一句话搞定:逐层向上(从右到左,从下到上)的向下调整。
代码如下

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
void buildHeap(T*array,int size){
delete []m_heap;
m_heap=array;
m_capacity=size;
m_heapSize=size--;
for (int i = (size-1)/2; i >=0; --i){
// 父节点索引
int index=i;
// 子节点索引
int child_index=2*index+1;
// 下浮父节点parent
T parent=m_heap[index];

// 向下调整
while (true){
if(child_index>=size)
break;
if(child_index+1<size&&m_heap[child_index]<m_heap[child_index+1])
child_index++;
if(parent>=m_heap[child_index])
break;
m_heap[index]=m_heap[child_index];

index=child_index;
child_index=index*2+1;
}
m_heap[index]=parent;
}
}

虽然该方法复杂度可以说是O(nlogn)O(n\log n),但比第一种方法要快很多。

堆排序

利用最大堆可以对数组升序排序,最小堆可以对数组降序排序。堆排序通过每次“删除”(交换数组首尾元素)堆顶元素(最大/小值),再重新构建二叉堆,使得数组内元素由后往前依次减小,从而数组变得有序。

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
void down(int *array,int size,int i){
int index=i;
int child_index=2*index+1;
int x=array[index];
while (true){
if(child_index>=size)
break;
if(child_index+1<size&&array[child_index]<array[child_index+1])
child_index++;
if(x>=array[child_index])
break;
array[index]=array[child_index];
index=child_index;
child_index=index*2+1;
}
array[index]=x;
}
void HeapSort(int *array,int size){
int index,child_index,parent,child;
// 构建堆,下到上
for (int i = (size-1-1)/2; i >=0; --i){
down(array,size,i);
}
// 交换数据后重新构建堆,上到下
for (int i = size-1; i >=0; --i){
swap(array[i],array[0]);
down(array,i,0);
}
}