堆和堆排序

1. 二叉树

二叉树最多只有左子树和右子树两个子树，二叉树的性质如下：

• 在二叉树的第层最多有个节点
• 深度为的二叉树最多有个节点
• 对于任意一棵二叉树，如果叶节点数为，而度数为2的节点总数为，则有
• 具有个节点的完全二叉树的深度必为#card=math&code=%5Clog2%28n%2B1%29&height=18&width=75)

常用的二叉树有满二叉树和完全二叉树，满二叉树指除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树；完全二叉树指当二叉树的深度为$h$，除第 $h$ 层外，其它各层 $(1 \sim h-1)$ 的结点数都达到最大个数，第 $h$ 层所有的结点都连续集中在最左边的二叉树。

对于一棵使用数组

• 左孩子：
• 右孩子：或者
• 父节点：

例如下图中索引为1的节点为2，那么它的父节点就是索引为0的节点1，它的左孩子为索引为3的节点4，右孩子是索引为4的节点5。

2. 堆概念

堆是一种经过排序的二叉树，它是数据结构中可以被看作是一棵树的数组对象，堆通常满足如下的两个性质：

• 堆中某个节点的值总是不大于或不小于其父节点值
• 堆总是一棵完全二叉树

堆通常有大根堆和小根堆两种：

• 大根堆：根节点的值大于左右子树的值，任意子树也是大根堆
• 小根堆：根节点的值小于左右子树的值，任意子树也是小根堆

例如：

3. 堆的构建

假设现在的数据为

如上所示，对的构建过程为：

• 2：此时堆为空，将2作为根节点
• 1：将1作为2的左孩子，构建完全二叉树，由于1 < 2，不执行交换操作
• 3：将3作为2的右孩子，由于3 > 2，将3和它的父节点2交换，此时3已是根节点，动作停止
• 6：将6作为1的左孩子，由于6 > 1，执行交换；由于 6 > 3，执行交换根节点
• 0：将0作为3的右孩子，由于 0 < 3，不执行交换
• 4：将4作为2的左孩子，由于 4 > 2， 执行交换；由于4 < 6，动作停止

代码实现：

import java.util.Arrays;
public class HeapTest {
    public static void main(String[] args) {
        int[] nums = {2,1,3,6,0,4};
        HeapSort(nums);
        System.out.println(Arrays.toString(nums));  // [6, 3, 4, 1, 0, 2]
    }
    public static void HeapSort(int[] nums) {
        // 如果数组为空或者只有一个元素，直接返回
        if (nums == null || nums.length < 2){
            return;
        }
        // 否则依次将数组中的节点插入到大根堆中
        for (int i = 0; i < nums.length; i++) {
            HeapInsert(nums, i);
        }
    }
    public static void HeapInsert(int[] nums, int i) {
        // 如果当前节点值大于它的父节点值，将其交换
        // 知道while中的条件不成立，即当前二叉树已是大根堆
        // 创建小根堆：while (nums[i] < nums[(i- 1) / 2]){...}
        while (nums[i] > nums[(i- 1) / 2]){
            swap(nums, i, (i - 1) / 2);
            // 更新需考虑的索引地址
            i = (i - 1) / 2;
        }
    }
    public static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        }
}

时间复杂度： 由于将新节点插入大根堆调整的过程中，只需要考虑根节点到当前节点路径上的值，那么值的个数也就是当前节点的层数，所以堆创建的时间复杂度为：

%20%3D%20%5Csum%7Bi%20%3D%201%7D%5E%7BN%7D%20%5Clog%20i%20%3D%20O(N)%0A#card=math&code=O%20%3D%20%5Clog1%20%2B%20%5Clog%202%20%2B%20…%20%2B%20%5Clog%28N%29%20%3D%20%5Csum%7Bi%20%3D%201%7D%5E%7BN%7D%20%5Clog%20i%20%3D%20O%28N%29%0A&height=47&width=325)

4. 堆的调整

假设经过上面的步骤已经将

实现代码：

import java.util.Arrays;
public class HeapTest {
    public static void main(String[] args) {
        int[] array = {6, 3, 4, 1, 0, 2};
        array[0] = 1;
        System.out.println(array);
        Heapify(array, 0, array.length);
        System.out.println(Arrays.toString(array)); // [4, 3, 2, 1, 0, 1]
    }
    // size表示堆的数值范围
    public static void Heapify(int[] array, int i, int size){
        // 看左右孩子
        int left = 2 * i + 1;
        while (left < size){
            // 右孩子为left + 1
            // 寻找左右孩子最大的哪那一个，将其索引赋给largest
            int largest = left + 1 < size && array[left + 1] > array[left] ? left+ 1 : left;
            // 判断largest指向的节点和当前节点的关系
            // 如果当前节点小于左右孩子中最大的节点，则更新largest
            largest = array[largest] > array[i] ? largest : i;
            // 如果当前已是大根堆，则跳出
            if (largest == i){
                break;
            }
            // 否则执行交换，继续往下判断
            swap(array, largest, i);
            i = largest;
            left = 2 * i + 1;
        }
    }
    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

5. 堆排序

经过前面的讲述，我们知道了如何根据给定的数组创建堆，并知道在数组中元素改变破坏已有的堆时如何进行调整，使其重新成为一个堆。那么如何根据堆的构建和堆的调整来实现堆排序呢？假设现在构建的是大根堆，那么堆的根节点值就是当前数组中的最大值，那么不断的弹出根节点然后再调整保持堆的性质，直到最后堆为空，那么依次弹出的节点值就是有序的，堆排序自然就完成了。

具体操作：在弹出根节点并调整堆的过程中使用一个变量size，它维护了数组中

• 将根节点和堆中最后一个元素交换，size减一
• 调整剩下的元素使其仍然为一个大根堆
• 不断重复上述过程，直到数组为空

代码实现：

import java.util.Arrays;
public class HeapTest {
    public static void main(String[] args) {
        int[] array = {2,1,3,6,0,4};
        HeapSort(array);
        System.out.println(Arrays.toString(array)); // [0, 1, 2, 3, 4, 6]
    }
    public static void HeapSort(int[] array) {
        if (array == null || array.length < 2){
            return;
        }
        for (int i = 0; i < array.length; i++) {
            HeapInsert(array, i);
        }
        // size维护数组中满足堆性质的区域
        int heap_size = array.length;
        // 交换根节点和数组的最后一个元素，更新size
        swap(array, 0, --heap_size);
        while (heap_size > 0){
            // 调整剩下的元素使其构成堆
            Heapify(array, 0, heap_size);
            swap(array, 0, --heap_size);
        }
    }
    public static void HeapInsert(int[] array, int i) {
        while (array[i] > array[(i- 1) / 2]){
            swap(array, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }
    public static void Heapify(int[] array, int i, int size){
        // 看左右孩子
        int left = 2 * i + 1;
        while (left < size){
            // 右孩子为left + 1
            int largest = left + 1 < size && array[left + 1] > array[left] ? left+ 1 : left;
            // 更新largest
            largest = array[largest] > array[i] ? largest : i;
            // 如果当前已是堆则跳出
            if (largest == i){
                break;
            }
            swap(array, largest, i);
            i = largest;
            left = 2 * i + 1;
        }
    }
    public static void swap(int[] array, int i, int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Python代码实现：

class HeapSort:
    def __init__(self, array):
        super().__init__()
        self.array = array
    def HeapSort(self):
        if self.array is None or len(self.array) < 2:
            return
        for i in range(len(self.array)):
            self.HeapInsert(i)
        heap_size = len(self.array)
        heap_size -= 1
        self.swap(0, heap_size)
        while heap_size > 0:
            self.Heapify(0, heap_size)
            heap_size -= 1
            self.swap(0, heap_size)
    def HeapInsert(self, index):
        while self.array[index] > self.array[(index - 1) // 2] and (index - 1) // 2 >= 0:
            self.swap(index, (index - 1) // 2)
            index = (index - 1) // 2 
    def Heapify(self, i, heapsize):
        left = 2 * i + 1
        right = 2 * i + 2
        while left < heapsize:
            if right < heapsize and self.array[right] > self.array[left]:
                largest = right
            else:
                largest = left
            largest = largest if self.array[largest] > self.array[i] else i
            if largest == i:
                break
            self.swap(largest, i)
            i = largest
            left = 2 * i + 1
    def swap(self, i, j):
        self.array[i], self.array[j] = self.array[j], self.array[i]
if __name__ == "__main__":
    array = [2,1,3,6,0,4]
    # array = [1, 3, 4, 1, 0, 2]
    heap = HeapSort(array)
    heap.HeapSort()
    # heap.Heapify(0, len(array))
    print (heap.array)

6. 算法复杂度

• 时间复杂度：#card=math&code=O%28N%20%2A%20%5Clog%20N%29&height=18&width=85)
• 空间复杂度：#card=math&code=O%281%29&height=18&width=30)
• 稳定性：不稳定