码上游记

hongjian.xia的个人博客

0%

二叉堆及堆排序

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

二叉堆概述

二叉堆（下文简称为堆）是一种优先队列，对于一个优先队列应该至少包含insert(插入)和deleteMin(删除最小者)两个操作。
堆具有 结构性 和 堆序性 两个性质。

堆的性质

结构性

堆是一颗 完全二叉树。所以对于一个高为$h$的完全二叉树有$ 2^h $到$2^{h+1}$个节点。这意味着有$N$个节点的完全二叉树的高为$\left\lfloor\log N\right\rfloor$（$\log N$向下取整）。
观察完全二叉树的结构，可以发现，我们存储完全二叉树不需要使用链表，用数组即可，只需要将元素按从上到下，由左至右的顺序依次存入数组（为方便计算，数组从下标1开始存储元素）。这时，对于数组任意位置上$ i(i \neq 0) $的元素，其左子节点在位置$2i$上，右子节点在左子节点之后的位置，即$2i+1$，它的父节点在位置$\left\lfloor i/2 \right\rfloor$上（此时$i \neq 1$）。

堆序性

堆任意节点应该小于它的所有后裔节点，从而有了“对于每一个节点$X$，$X$的父节点元素应小于或等于$X$，根节点除外”，这就是堆序性（小堆，相反则是大堆）。

堆的实现

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
public class BinaryHeap<T extends Comparable<? super T>> {
	private static final int DEFAULT_CAPACITY = 10;
	private T[] items;
	private int currentSize;
	
	public BinaryHeap() {
		this(DEFAULT_CAPACITY);
	}
	
	public BinaryHeap(int capacity) {
		if (capacity < 0) 
			capacity = DEFAULT_CAPACITY;
		items = createArray(capacity);
	}
	
	public BinaryHeap(T[] items) {
		this(items == null ? DEFAULT_CAPACITY : items.length);
		if (items != null) {
			currentSize = items.length;
			System.arraycopy(items, 0, this.items, 1, currentSize);
			buildHeap();
		}
	}
	
	public boolean isEmpty() {
		return currentSize == 0;
	}
	
	public void clear() {
		currentSize = 0;
		items = createArray(DEFAULT_CAPACITY);
	}
	
	public T findMin() {
		if (currentSize < 1) 
			throw new NoSuchElementException();
		return items[1];
	}
	
	public void insert(T item) {
		if (currentSize == items.length - 1) {
			enlargeArray((items.length << 1) + 1);
		}
		int hole = ++currentSize;
		for (items[0] = item; item.compareTo(items[hole >> 1]) < 0; hole >>= 1) {
			items[hole] = items[hole >> 1];
		}
		items[hole] = item;
	}
	
	public T deleteMin() {
		if (isEmpty())
			throw new NoSuchElementException();
		T min = findMin();
		items[1] = items[currentSize--];
		percolateDown(1);
		
		return min;
	}
	
	private void percolateDown(int hole) {
		int child;
		T tmp = items[hole];
		for (; hole << 1 <= currentSize; hole = child) {
			child = hole << 1;
			if (child != currentSize && items[child + 1].compareTo(items[child]) < 0) {
				child++;
			}
			if (items[child].compareTo(items[hole]) < 0) {
				items[hole] = items[child];
			} else {
				break;
			}
		}
		items[hole] = tmp;
	}
	
	private void buildHeap() {
		for (int i = currentSize >> 1; i > 0; i--) {
			percolateDown(i);
		}
	}
	
	@Override
	public String toString() {
		return "BinaryHeap [items=" + Arrays.toString(items) + ", currentSize=" + currentSize + "]";
	}

	@SuppressWarnings("unchecked")
	private void enlargeArray(int newSize) {
		T[] tmp = (T[]) new Comparable[newSize];
		System.arraycopy(items, 1, tmp, 1, currentSize);
		items = tmp;
	}
	
	@SuppressWarnings("unchecked")
	private T[] createArray(int capacity) {
		return (T[]) new Comparable[capacity + 1];
	}
	
	public static void main(String[] args) {
		BinaryHeap<Integer> heap = new BinaryHeap<>(new Integer[] {2, 5, 7, 9, 1});
		for (int i = 10; i > 0; i--)
			heap.insert(i);
		System.out.println("Min:" + heap.findMin());
		System.out.println(heap);
	}
}

堆排序

堆排序是使用二叉堆进行排序的一种排序算法。

堆排序实现

这里堆是从数组下标0开始存储的，所以子节点位置的计算和之前的有略微不同。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class HeapSort {
    
    private static int leftChild(int i) {
        return 2 * i + 1;
    }
    
    private static <T extends Comparable<? super T>> void percolateDown(T[] arr, int i, int n) {
        T temp = arr[i];
        int child;
        for (; leftChild(i) < n; i = child) {
            child = leftChild(i);
            
            // child != n - 1意味着i还有右孩子
            if (child != n - 1 && arr[child+1].compareTo(arr[child]) > 0) {
                child++;
            }
            
            // 小于temp，空穴中应该放入temp
            if (temp.compareTo(arr[child]) > 0) {
                break;
            } else {
                // 空穴下移一层
                arr[i] = arr[child];
            }
        }
        arr[i] = temp;
    }
    
    private static <T extends Comparable<? super T>> void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static <T extends Comparable<? super T>> void heapSort(T[] arr) {
        // build max heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            percolateDown(arr, i, arr.length);
        }
        
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            percolateDown(arr, 0, i);
        }
    }
    
    public static void main(String[] args) {
        Integer nums[] = {2, 83, 34, 12, 78, 39, 20};
        heapSort(nums);
        Stream.of(nums).forEach(System.out::println);
    }

}

堆排序的时间复杂度

堆排序的时间复杂堆为$O(N\log N)$。堆排序需要进行$N$次deleteMin操作，每次deleteMin操作的时间复杂度为$O(\log N)$，因此总的时间复杂度为$O(N\log N)$。

源码

算法完整源码

参考

MarkAllenWeiss. 数据结构与算法分析:Java语言描述-第3版[M]. 机械工业出版社, 2016, 156-164,191-193