六.堆排序

六.堆排序

一.二叉堆基本简介

本质上是一个数组,根据下标等价为一个完全二叉树,对堆的索引实质上是对下标的浮动

具有两种形式: 最大堆(父节点比子节点要大)\最小堆(父节点比子节点要小)

基本Index操作

父节点 Parent(i){return i/2(ceil)}

左节点 Left-Child(i){return i*2}

右节点 Right-Child(i){return i*2+1}

将堆各种操作组合起来即可以构成新的算法或新数据结构

堆排序过程: 是利用Heap数据结构的性质来排序,需要三个操作Build-Heap(子过程Max-Heapify)和Heap-Sort

 优先队列结构: 在Heap

二.(二叉)堆排序

维护性质Max-Heapify

Max-Heapify

Max-Heapify(A,i){
	left = Left-Child(i)
	right = Right-Child(i)
	
	init max_index = i;
	{
		if(A[left]>A[max_index]) max_index = left ;
		if(A[right]>A[max_index]) max_index = right;
	}
	
	if(max_index == i){ return ;}
	else{
		Exchange-Value(A,i,max_index)
		Max-Heapify(A,max_index)
		return ;
	}
}

Copy

代码解析

复杂度: O(lgn)O(lgn)O(lgn)﻿

使用条件: 

子节点(子树)已经成为了最大堆,仅仅只有A[i]—Left-Child[i]—Right-Child[i] 这个三元组不满足最大堆

这个Max-Heapify只能向下维护堆的性质,当因为A[i]与Child交换导致A[i].Parent与交换后的A[i]之间违背堆的性质时候,无法维护.

但是在特殊结构下,即A[i].Child<A[i].Parent时候,却也能保证向上不维护堆的性质,我们不妨将该状态定义为 "小于形准堆"

比较父节点,两个子节点Value的大小,并找到最大Value对应的Index(max_index)

交换父节点(i)和(max_index)中对应的值

交换后情况判断

若无交换,则目前恰好为最大堆

若有交换,则子树可能不满足最大堆定义,需要递归调用

小于形准堆 

定义: 有办法通过只增大一个元素A[i],使得整个堆恢复性质

性质: 假设A[i] A[i].Left-Child A[i].Right-Child三元组不满足堆性质,只需要调用Max-Heapify即可恢复,且能保证以交换后A[i]与A[i].Parent符合堆的规则

建堆Build-Max-Heap

Build-Max-Heap

Build-Max-Heapify(A)
	init i = A.length
	for i = A.length/2 to 1
	{
		Max-Heapify(A,i)
	}

Copy

代码解析

从堆底部开始迭代调用,保证了每次调用都满足Max-Heapify的条件(子树已满足最大堆要求)

复杂度: 

简单分析: 由于该算法调用O(n)O(n)O(n)﻿次Max-Heapify,同时Max-Heapify复杂度为O(lgn)O(lgn)O(lgn)﻿,则有复杂度O(nlgnnlgnnlgn﻿),但是实际上详细证明可知道为O(n)O(n)O(n)﻿

完整分析:

 T(n)=∑h=0⌊log2n⌋⌈n2h+1⌉O(h)=O(n∑h=0⌊log2n⌋h2h)=O(n∑h=0∞h2h)=O(n∗C)=O(n)T(n) = \sum\limits_{h=0}^{\lfloor log_2n \rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h) = O(n\sum\limits_{h=0}^{\lfloor log_2n \rfloor}\frac{h}{2^h})  = O(n\sum\limits_{h=0}^{\infty}\frac{h}{2^h})=O(n*C)=O(n)T(n)=h=0∑⌊log2​n⌋​⌈2h+1n​⌉O(h)=O(nh=0∑⌊log2​n⌋​2hh​)=O(nh=0∑∞​2hh​)=O(n∗C)=O(n)﻿

渐进符号运算律-替代包括律: 将O(h)O(h)O(h)﻿用K∗hK*hK∗h﻿替代(k为常数),在最后的结果再用中用O(...)O(...)O(...)﻿包括

其中⌊log2n⌋\lfloor log_2n \rfloor⌊log2​n⌋﻿代表堆的高度(扣除最后不完整的一层)

第h层中节点分析: N=2i=2⌊log2n⌋−h=⌊n⌋2hN=2^i=2^{\lfloor log_2n\rfloor-h}=\frac{\lfloor n \rfloor }{2^h}N=2i=2⌊log2​n⌋−h=2h⌊n⌋​﻿ 代表第h层中节点个数
(剔除不完整的最后一层,最底下为第0层)

为何自己推导的 ⌊n⌋2h≠⌈n2h+1⌉\frac{\lfloor n \rfloor }{2^h} \neq \lceil\frac{n}{2^{h+1}}\rceil2h⌊n⌋​=⌈2h+1n​⌉﻿: 课本上的h不代表第几层,而代表其子树层数,而上面NNN﻿则代表着有h层的节点有多少个,于是会有少量的不同

Heap-Sort

Heap-Sort代码

Heap-Sort(A)
{
	Build-Heap(A)
	for i = A.length to 2
		exchange A[i] , A[1]
		A.heap-size = A.heap-size - 1
		Max-Heapify(A)
}

Copy

代码分析

将最大的元素弹出后,关键是如何看待剩下的元素

第一种是直接对A[2..n]再使用一次Build-Max-Heap,但是由于破坏了堆的结构,用时很长

第二种则是将堆底部元素置换到A[1],对堆的结构破坏比较小

三.优先队列

简介: 在堆排序的基础操作(Build-Heap ; Heap-Sort ; Max-Heapify)上,增加了几个新的操作

Maxinum(A) {return A[1]} ; : 直接返回A[1]即可

Extract-Max(A) ; : 

相当于Heap-Sort循环迭代中的一次迭代

显然有A[length]<A[1]则该情况为小于形准堆 通过Max-Heapify即可恢复

破坏堆节点的恢复 : 这三个操作都是通过破坏了一个堆节点,来打破了堆的性

Insert(A,x) ; 

将Insert元素放在堆底,比较X元素的X.Uncle元素,X.Parent元素三者的大小,并交换

基本思路很类似Build-Max-Heap,但是不需要对每一层的所有元素调用,只需要对关联的的支路调用

不像Max-Heapify,交换后会破坏子树结构,该结构中x.Parent与x交换之后,由于原来是Max-Heap的结构,Parent>x>x.child所以,不会破坏子树结构,不需要调用Max-Heapify向下恢复堆的结构,即 "大于形准堆"

Increase-Key(A,Old,New)  : 和Insert(A,x)同理,都是将一个元素增大,变成 大于形准堆,只需要调用一次Max-Heapify-2nd即可恢复

Max-Heapify-2nd

Max-Heapify-2nd

Max-Heapify-2nd(A,i){
	uncle = uncle(i)
	parent = parent(i)
	
	init max_index = i;
	{
		if(A[uncle]>A[max_index]) max_index = uncle;
		if(A[parent]>A[max_index]) max_index = parent ;
	}
	
	if(max_index == i){ return ;}
	else{
		Exchange-Value(A,i,max_index)
		Max-Heapify(A,max_index)
		return ;
	}
}

Copy

代码上几乎和Max-Heapify一致,只是需要考虑的是考虑A[i] A[i].Uncle A[i].Parent这个三元组的大小比较

将Build-Max-Heap中Max-Heapify中替换为Max-Heapify-2nd也可构造第二个版本的Max-Heapify-2nd

大于形准堆与Max-Heapify-2nd

大于形准堆定义: 有办法通过只减小一个元素A[i],使得整个堆恢复性质(A[i]大于理想值)

我们将插入元素到最大堆中视作将堆中一个元素增大,从原先的−∞-\infty−∞﻿ 增大到某个值

正如维护小于形堆的性质有对应的操作Max-Heapify ,我们也构造对称的操作Max-Heapify-2nd

三.堆的统一

统一方法

除了堆这个数据结构以外以外注意两种伴生准堆

通过堆  ⟺  \iff⟺﻿两种准堆 转换和恢复,可构造各种堆的操作

小于型准堆

上层方法: Delete(A,x) ;   Decrease-Key(A,Old,New) ; Extract-Max(A) ; 

底层方法: Max-Heapify

大于型准堆

上层方法: Insert(A,x) ;   Increase-Key(A,Old,New) ; 

底层方法: Max-Heapify-2nd 

建堆: 通过Max-Heapify-2nd  或者 Max-Heapify 都可以