堆排序

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

堆排序

最大堆,最小堆:

  • 最大堆：
    堆的最大元素存放在根结点中。并且，在任一子树中，该子树所包含的所有结点的值都不大于该子树根结点的值。即：A[PARENT(i) ≥ A[i]。堆排序使用最大堆。
  • 最小堆：
    堆的最小元素存放在根结点中。并且，在任一子树中，该子树所包含的所有结点的值都不小于该子树根结点的值。即：A[PARENT(i) ≤ A[i]。最小堆常用来构造优先队列。

将数组A看成一颗近似完全二叉树:

  • 树的第一个根节点是A[0],最后一个根节点A[len(A)//2 - 1]
  • 假定一个结点下标是i,则它的父节点,左孩子,右孩子下标如下:
    1
    2
    LEFT(i) : return 2i+1 
    RIGHT(i) : return 2i+2
  1. 如何建最大堆
  2. 如何维护最大堆
  3. 排序
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
package cn.llnn.sort;

import java.util.Arrays;

/**
 * 堆排序,最大堆
 *
 * @author llnn
 * @create 2019-09-26 12:57
 **/
public class HeapSort {
    private static int heapSize;

    public static void main(String[] args) {
        int[] a = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
        System.out.println("待排序:" + Arrays.toString(a));
        heapSort(a);
        System.out.println("结果:" + Arrays.toString(a));
    }

    private static void heapSort(int[] a) {
        heapSize = a.length;
        buildMaxHeap(a);
        System.out.println("最大堆:" + Arrays.toString(a));
        System.out.println("==============");
        for (int i = a.length - 1; i >= 0; i--) {
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            // 调整数组大小
            heapSize--;
            adjustHeap(a, 0);
            System.out.println(Arrays.toString(a));
        }
        System.out.println("==============");
    }

    private static void buildMaxHeap(int[] a) {
        for (int i = heapSize / 2; i >= 0; i--) {
            adjustHeap(a, i);
        }
    }

    private static void adjustHeap(int[] a, int root) {
        int large = root;
        int leftChild = 2 * root + 1;
        int rightChild = 2 * root + 2;
        // 最小堆 a[leftChild] < a[root]
        if (leftChild < heapSize - 1 && a[leftChild] > a[root]) {
            large = leftChild;
        }
        // 最小堆 a[leftChild] < a[root]
        if (rightChild < heapSize - 1 && a[rightChild] > a[large]) {
            large = rightChild;
        }


        if (large != root) {
            int temp = a[root];
            a[root] = a[large];
            a[large] = temp;
            adjustHeap(a, large);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
待排序:[51, 46, 20, 18, 65, 97, 82, 30, 77, 50]
最大堆:[97, 77, 82, 46, 65, 20, 51, 30, 18, 50]
==============
[82, 77, 51, 46, 65, 20, 50, 30, 18, 97]
[77, 65, 51, 46, 18, 20, 50, 30, 82, 97]
[65, 46, 51, 30, 18, 20, 50, 77, 82, 97]
[51, 46, 50, 30, 18, 20, 65, 77, 82, 97]
[50, 46, 20, 30, 18, 51, 65, 77, 82, 97]
[46, 18, 20, 30, 50, 51, 65, 77, 82, 97]
[30, 18, 20, 46, 50, 51, 65, 77, 82, 97]
[20, 18, 30, 46, 50, 51, 65, 77, 82, 97]
[18, 20, 30, 46, 50, 51, 65, 77, 82, 97]
[18, 20, 30, 46, 50, 51, 65, 77, 82, 97]
==============
结果:[18, 20, 30, 46, 50, 51, 65, 77, 82, 97]

https://ictar.xyz/2015/12/07/%E4%B9%9D%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E5%8F%8A%E5%85%B6Python%E5%AE%9E%E7%8E%B0%E4%B9%8B%E5%A0%86%E6%8E%92%E5%BA%8F/