title: 堆 date: 2021-08-13 10:26:18 categories:

数据结构

tags:

数据结构

前言

本文的内容参考自《算法导论第三版》第六章堆排序，相比于原文，少了复杂的证明，简单直述堆的性质、维护操作以及实际使用。实现逻辑使用伪代码进行描述，如果看不懂伪代码，可以直接看文末的附录代码，附录代码使用Java实现。

堆定义

(二叉)堆是一个树形结构的数组对象(也可以使用链表表示),其可以被视为一颗完全二叉树.,每层最终都会被填满,因此可以使用数组来存储,不会浪费空间

满二叉树是指除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树。

完全二叉树是一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

使用数组A表示的堆具有以下属性

length[A]是数组中的个数
heap-size[A]是堆中元素的个数
h(A) = log2(length(A)) + 1, h(A)是二叉树的高

A[1...length[A]]都可以包含有效的元素,但是heap-size[A]之后的元素都不属于任何堆,简单来理解就是该结点是空的,此时heap-size[A] ≤ length[A].

假设树的根是A[1], 给定某个结点的下标i,那么结点i的父结点parent(i),左子结点left(i)和右子结点right(i)都可以简单的计算出来.

parent(i) = A[floor(i/2)]

left(i) = A[2i]

right(i) = A[2i+1]

需要注意的一点是, floor(i/2)是下取整

.png

图一堆与数组的关系,这是一个最小堆

堆性质

二叉堆有两种: 最大堆(大顶堆),最小堆(小顶堆). 堆中的结点需要满足堆特性,细节因为堆类型不同而有所差别.

在最大堆中,A[parent(i)] ≥ A[i],也就是说结点A[i]必须小于等于父结点A[parent(i)]

在最小堆中,A[parent(i)] ≤ A[i],也就是说结点A[i]必须大于等于父结点A[parent(i)]

本文以最大堆为例,讲述如何进行堆性质维护,堆构建,堆排序算法以及优先队列的构建

堆的维护

保持堆性质

维持堆的性质是堆的最重要的操作. 定义MAX-HEAPIFY(A,i),指代维护以数组A构建的堆中结点i的堆性质,保证A[i]结点及A[i]结点的左子树与右子树满足最大堆性质. 假定A[i]结点的左子树和右子树已经满足了最大堆的性质

实现伪码:

MAX-HEAPIFY(A,i) 
l <- left(i)
r <- right(i)
if l <= heap-size(A) && A[l] > A[i]
		lagest = l
else 
		lagest = i
if r <= heap-size[A] && A[r] > A[i]
lagest = r
else
lagest = i
if lagest != i
swap(A[i],A[lagest])
MAX-HEAPIFY(A,lagest)

.png

图二维护堆的性质

如图二(a)所示,给定一个堆,假设现在需要维护A[2]的堆性质,首先找到A[2]左,右子结点中最大的一个,与其交换位置,交换后结果如图二(b);A[2]与A[5]交换位置后,还是不满足最大堆性质,因此继续调用MAX-HEAPIFY(A,5)维持以A[5]为根的堆的性质,交换A[5]与A[10]; 第二次交换完成的结果如图二(c)所示,此时已经满足堆性质,不需要在做其他处理.

MAX-HEAPIFY(A,i)作用在一颗以结点i为根的,大小为n的子树上时,调整的总时间为调整单个结点的时间O(1)加上递归子结点的时间, 当i结点的子树大小至多为2n/3 时(完全二叉树最后一层半满)为最坏情况,因此MAX-HEAPIFY的时间复杂度为 O(lgn) 即树的高度.

由于递归调用依赖栈，因此在一些无法使用栈的系统上将会受到限制，因此可以将递归调用的算法替换为循环算法。

伪代码如下：

MAX-HEAPIFY(A,i)
while i < heap-size[A]
	l <- left(i)
	r <- right(i)
	if l <= heap-size(A) && A[l] > A[i]
			lagest = l
	else 
			lagest = i
if r &lt;= heap-size[A] &amp;&amp; A[r] &gt; A[i]
		lagest = r
else 
		lagest = i
if lagest != i
swap(A[i],A[lagest])
i = lagest

此处需要解释下完全二叉树最后一层半满的时候左子树的结点数量为2n/3.

因为:

右子树的数量:

1 + 2 + 2^2 + ... + 2^(h-3) = 2^(h-2) -1

左子树的数量

1 + 2 + 2^2 + ... + 2^(h-3) + 2^(h-2) = 2*2^(h-2) -1

所以:

n = 左子树的数量 + 右子树数量 + 1

n = (2*2^(h-2) -1) + (2^(h-2) -1) +1

n = 3*2^(h-2) -1

所以:

2^(h-2) = (n+1)/3

所以左子树的结点数量最大为

2*2^(x-2) -1 = 2 * ((n+1)/3) - 1= 2n/3 - 1/3 < 2n/3

因此左子树的最大结点数量不操作2n/3

堆的初始化

可以自底向上使用MAX-HEAPIFY将一个数组A[1...n]调整为一个最大堆. 给定的一个数组A,默认可以认为是一个不满足的堆性质的普通二叉树,二叉树的叶子结点都可以认为是一个只含一个元素的堆. 二叉树中最后一个元素A[n]的父结点为parent(n) = floor(n/2), A[parent(n)...n]都是二叉树的子结点. 因此从parent(n)开始应用MAX-HEAPIFY将会把每个子结点维护成满足最大堆性质,当维护到根结点时整颗二叉树就是一个最大堆.

伪代码:

BUILD-MAX-HEAP(A):
heap-size[A] ← length[A]
for i <- floor(length[A]/2) downto 1
MAX-HEAPIFY(A,i)

.png

图三建堆

首先访问的是parent(11),即A[11]的父结点A[5],如图三(a),由于A[5] < A[10],因此发生交换,变为图三(b),A[11]没有子结点了,所以一次MAX-HEAPIFY(A,5)结束
访问A[4],由于A[4]对应的子树满足堆性质,MAX-HEAPIFY(A,4)处理结束,如图三(c)
访问A[3],由于A[3]< A[6],因此交换A[3]和A[6],A[6]无子结点,结束MAX-HEAPIFY(A,3),如图三(d)-(e)
访问A[2],由于A[2]< A[5],交换A[2]和A[5], MAX-HEAPIFY(A,2)中递归调用MAX-HEAPIFY(A,5),检查到A[5]所在子树不满足最大堆性质,交换A[5]和A[11],最后MAX-HEAPIFY(A,2)调用完成. 如图三(f)-(h)
访问A[1],满足最大堆性质,如图三(j)

初始化堆的时候，对于每个非叶子结点，都要调用上述函数，将它与它的孩子结点进行比较和交换，顺序是从后向前。

以操作2作为基本操作，对每一层都完全铺满的堆进行分析，

设元素个数为n，则堆的高度k=log（n+1）≈log n，非叶子结点的个数为2^（k-1）-1

假设每个非叶子结点都需要进行调整，则第i层的非叶子结点需要的操作次数为k-i，

第i层共有2^（i-1）个结点，则第i层的所有结点所做的操作为k2^（i-1）- i2^（i-1），

共k-1层非叶子结点，总的操作次数为

$\displaystyle \sum\_{i=1}^{k-1} \left( k2^{i-1} - i2^{i-1} \right)$

化简可得，上式=2^k-k+1，将k=log（n+1）≈log n代入，得n - log n +1，

所以，初始化堆的复杂度为O(n)

获取最大值

最大堆的根就是最大值,因此HEAP-MAX=A[1]

插入元素

将一个元素添加到堆中，先将该元素按照完全二叉树的定义放置在最尾部，使用数组表示则是A[heap-size[A]+1]，添加到堆中的元素可能会违反最大堆性质，因此可以沿着叶子结点到根的路径寻找一个可插入位置，不断与父结点进行比较，如果比父结点大就与父结点交换，最大堆的性质将能够得到保证。

伪代码：

MAX-HEAP-INSERT(A,key)
heap-size[A] <- heap-size[A] + 1
i <- heap-size[A] 
while i > 1 && A[i] > parent(i)
		swap(A[i],parent(i))
		i <- parent(i)

.png

图四添加堆元素

添加元素到数组末尾，结点编号为i=12,如图四（a）
与父结点A[5]比较，并进行交换, 此时上升到i=5，如图四（b）
与A[2]比较，并进行交换，此时上升到i=2, 如图四（c）
与A[1]比较，并进行交换，此时上升到i=1, 如图四（d）
由于i 不大于1，所以终止循环条件，结束添加

插入一个元素的时间复杂度为O(lgn),最大耗时是需要沿着叶结点到根的路径进行上升维护堆性质

移除最大元素

移除A[1]后，A[1]原来的位置需要选取一个元素来填充，选取A[heap-size[A]]替换A[1], 这样其他子树的最大堆性质都能得到满足，问题就回归到了维护结点i的堆性质问题

伪代码如下：

MAX-HEAP-REMOVE(A)
if heap-size[A] < 1
	  throw error "heap underflow"
max <- A[1]
A[1] <- A[heap-size[A]]
heap-size[A] <- heap-size[A]-1
MAX-HEAPIFY(A,1)
return max

移除指定的元素

将指定的元素A[i]移除，为了保证最大堆的完全二叉树的性质，需要使用A[heap-size[A]]，最后一个堆元素替换掉移除的指定元素A[i]。替换后可能会违反最大堆的性质，因此需要维护以A[i]为根的子树的最大堆性质。替换的结点A[i]还需要沿着到根的路径上升，保证整体最大堆性质。

因此移除指定元素是维护堆性质MAX-HEAPIFY和插入结点MAX-HEAP-INSERT子程序的合成使用.具体实现伪代码如下：

MAX-HEAP-REMOVE(A,i)
if heap-size[A] < 1
    throw error "heap underflow"
if heap-size[A] < i 
    throw error "index out of bounds"
target <- A[i]
last = heap-size[A]
A[i] <- A[last]
heap-size[A] <- heap-size[A] - 1
if i == last
	return target
MAX-HEAPIFY(A,i)
while i > 1 && A[i] > A[parent(i)]
    swap(A[i],A[parent(i)])
    i <- parent(i)
return target

实际上，替换后的元素要么下沉，要么就是上升，最大复杂度为O(logN)

堆应用

构建优先队列

队列是一个先进先出的结构，其基本操作是向队尾添加元素和移除队首元素，使用最大堆可以构建一个最大优先级队列。移除队首元素就是移除堆顶元素，堆顶元素是优先级最高的元素，通过MAX-HEAP-INSERT完成队列的入队功能。向队尾添加元素就是在堆底添加元素，使用MAX-HEAP-REMOVE完成队列的出队功能，堆底元素都是优先级较低的元素。

堆排序

给定一个特定的含有n个元素的数组，将其按升序排序。一开始，可以使用BUILD-MAX-HEAP来初始化一个最大堆。最大堆的最大值元素在A[1],将其与A[n]交换位置，最大值也就交换到了正确的位置，剩余需要排序的内容应该是A[1....n-1]。将结点n从堆中“移除”后，A[1]的左子树和右子树仍然保持了最大堆性质，只有A[1]可能违反了最大堆性质，此时可以通过调用MAX-HEAPIFY(A,1)快速重新构建为一个最大堆。不断重复该过程，将n-1下降到2时，整个堆只剩下A[1],此时整个堆已经完成了排序。

伪代码如下：

HEAPSORT(A)
MAX-HEAP-BUILD(A)
for i<-heap-size[A] downto 2
    swap(A[1],A[i])
    heap-size[A] <- heap-size[A] - 1
    MAX-HEAPIFY(A,1)

.png

图五堆排序过程

有连接线代表元素还处于堆中，无连线代表已经将元素从堆中移除,是一个孤立元素。一开始先将A[1]与堆中的最后一个元素交换位置，将最后一个元素从堆中移除，再使用MAX-HEAPIFY(A，1)维护剩余元素所在堆的性质，这样循环调用，最终将会得到一个有序的数组

附录

最大堆实现

package tree;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MaxHeap<T extends Comparable<T>> {
// 堆底层存储容器
List<T> A;
// 堆大小
private int heapSize;
public MaxHeap() {
A = new ArrayList&lt;&gt;();
}
public MaxHeap(int cap) {
A = new ArrayList&lt;&gt;(cap);
}
public MaxHeap(List&lt;T&gt; arr) {
if (arr == null) {
throw new IllegalArgumentException(&quot;array is null&quot;);
}
A = new ArrayList&lt;&gt;(arr.size());
A.addAll(arr);
// 建堆
maxHeapBuild();

}
/**

假设A[i]的左子树和右子树都是满足最大堆性质，调用该方法维护以A[i]为根的子树的最大堆性质

@param i 结点i的下标
*/
private void maxHeapify(int i) {
while (i &lt;= lastNodeIndex()) {
int l = left(i);
int r = right(i);
int largest = i;
if (l &lt;= lastNodeIndex() &amp;&amp; A.get(l).compareTo(A.get(i)) &gt; 0) {
largest = l;
}
if (r &lt;= lastNodeIndex() &amp;&amp; A.get(r).compareTo(A.get(largest)) &gt; 0) {
largest = r;
}
if (largest != i) {
swap(A, i, largest);
i = largest;
} else {
break;
}
}
}

/**

建堆
*/
private void maxHeapBuild() {
heapSize = A.size();
for (int i = parent(lastNodeIndex()); i &gt;= 0; i--) {
maxHeapify(i);
}
}

/**

像堆中插入元素

@param x
*/
public void maxHeapInsert(T x) {
if (x == null) {
throw new IllegalArgumentException(&quot;element can't be null&quot;);
}
A.add(x);
heapSize++;
int i = lastNodeIndex();
while (i &gt; 0 &amp;&amp; A.get(i).compareTo(A.get(parent(i))) &gt; 0) {
swap(A, i, parent(i));
i = parent(i);
}
}

/**

移除堆顶元素

@return 移除元素
*/
public T maxHeapRemove() {
T max = A.get(0);
int last = lastNodeIndex();
swap(A, 0, last);
A.remove(last);
heapSize--;
maxHeapify(0);
return max;
}

/**


移除指定元素



@param i 元素下标


@return 返回移除元素
*/
public T maxHeapRemove(int i) {
if (i &gt;= heapSize) {
throw new ArrayIndexOutOfBoundsException();
}
T target = A.get(i);
// 先替换元素，并维护子树最大堆性质
int last = lastNodeIndex();
swap(A, i, last);
A.remove(last);
heapSize--;
if (i == last) {
return target;
}
maxHeapify(i);
//上升维护
while (i &gt; 0 &amp;&amp; A.get(i).compareTo(A.get(parent(i))) &gt; 0) {
swap(A, i, parent(i));
i = parent(i);
}
return target;
}


private void swap(List&lt;T&gt; A, int a, int b) {
T t = A.get(a);
A.set(a, A.get(b));
A.set(b, t);
}
private int parent(int i) {
return (i - 1) / 2;
}
private int left(int i) {
return 2 * i + 1;
}
private int right(int i) {
return 2 * (i + 1);
}
private int lastNodeIndex() {
return heapSize - 1;
}
public int heapSize() {
return heapSize;
}
public static void main(String[] args) {
List&lt;Integer&gt; t = Arrays.asList(1, 2, 3, 10, 20, 9, 8);
// 20 10 9 1 2 3 8
MaxHeap&lt;Integer&gt; maxHeap = new MaxHeap&lt;&gt;(t);
System.out.println(maxHeap);
// 30 20 9 10 2 3 8 1
maxHeap.maxHeapInsert(30);
// 20 10 9 1 2 3 8
Integer x = maxHeap.maxHeapRemove();
System.out.println(x);
// 20 8 9 1 2 3
Integer y = maxHeap.maxHeapRemove(1);
System.out.println(y);
}

}

堆排序

package sort.heap;
import sort.ISort;
import java.util.Arrays;
public class HeapSort<T extends Comparable<T>> implements ISort<T> {
/**
 * 排序
 *
 * @param data 待排数据
 * @return 排序后列表
 */
@Override
public T[] sort(T[] data) {
    // 堆初始化
    maxHeapBuild(data);
    // 执行堆排序
    for (int i = lastNodeIndex(data.length); i &gt; 0; i--) {
        swap(data, 0, i);
        maxHeapify(data, i, 0);
    }
    return data;
}
private void maxHeapBuild(T[] data) {
for (int i = parent(lastNodeIndex(data.length)); i &gt;= 0; i--) {
maxHeapify(data, data.length, i);
}
}
private void maxHeapify(T[] data, int heapSize, int i) {
while (i &lt;= lastNodeIndex(heapSize)) {
int l = left(i);
int r = right(i);
int largest = i;
int last = lastNodeIndex(heapSize);
if (l &lt;= last &amp;&amp; data[l].compareTo(data[i]) &gt; 0) {
largest = l;
}
if (r &lt;= last &amp;&amp; data[r].compareTo(data[largest]) &gt; 0) {
largest = r;
}
if (largest != i) {
swap(data, i, largest);
i = largest;
} else {
break;
}
}
}
private int parent(int i) {
return (i - 1) / 2;
}
private int left(int i) {
return 2 * i + 1;
}
private int right(int i) {
return 2 * (i + 1);
}
private int lastNodeIndex(int len) {
return len - 1;
}
private void swap(T[] data, int a, int b) {
T t = data[a];
data[a] = data[b];
data[b] = t;
}
public static void main(String[] args) {
Integer[] arr = new Integer[10];
arr[0] = 10;
arr[1] = 9;
arr[2] = 8;
arr[3] = 7;
arr[4] = 6;
arr[5] = 5;
arr[6] = 4;
arr[7] = 3;
arr[8] = 2;
arr[9] = 1;
HeapSort&lt;Integer&gt; sort = new HeapSort&lt;&gt;();
sort.sort(arr);
Arrays.stream(arr).forEach(System.out::println);
}

}