从优先队列到实现堆排序

从优先队列到实现堆排序

介绍

优先队列即为堆，使用二叉树的结构维护节点与子节点的关系，从而维护根与后续除了根的其他节点的关系，根为最值节点。可以表达为 根 “大于” 直接子代， 直接子代 “大于” 直接子代的子代 ，相当于第一层节点大于第二层节点，第二层大于第三层…从而第一层大于所有层。

节点是以完全二叉树的形式存储。我们使用数组模拟二叉树的结构，因此父亲节点与子代节点存在关系为“父节点下标*2* + 1= 左节点下标 父节点下标*2* + 2= 右节点下标 ”

JDK提供的实现

实现：使用插入建堆，插入时维护小(大)堆。

public class TestPriorityQueue {

    public static void main(String[] args) {
        //默认是小根堆
       PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        int[] arr = {6,2,9,4,5};
        for(int num : arr){
            //插入
            priorityQueue.offer(num);
            System.out.println(priorityQueue);
        }
    }
}
/*
[6]
[2, 6]
[2, 6, 9]
[2, 4, 9, 6]
[2, 4, 9, 6, 5]
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

小根堆结构如下图，父亲节点小于子代节点

tips:大根堆需要加上一个自定义的比较器类即可，如new PriorityQueue<>((a,b) -> b-a);

自己实现小根堆

时空复杂度O(n) 证明https://blog.csdn.net/anonymalias/article/details/8807895

思路：已知我们有一个无序的数组，需要实现为具有堆特性的数组。数组长度为n。

• 使用建堆。我们维护父节点从而维护整个数组。我们从下标最大的节点的父节点开始处理。为什么是最大下标呢？因为“插入”建堆时，如果发生“交换”会递归走向下层节点。如果大到小的顺序进行维护，下层节点必然满足 父节点 小于 子节点，如果发生交换，那么更换后的父节电必然满足比之前的父亲节点更小（因为是更小才发生交换的啊），因此在下层节点则不需要再次比较遍历。此时便可以去除递归代码。

  反证法证明

  从最小下标开始

结合代码实例讲解

public class TestPriorityQueue {

    public static void main(String[] args) {
        int[] arr = {6,2,9,4,5};
        new Heap().buildMinHeap(arr, arr.length);
        for (int i : arr) {
            System.out.print(i);
        }
    }
}

class Heap{

    public void buildMinHeap(int[] nums,int len) {
        for(int i = len/2;i>=0;i--){
            maxHeapify(nums,i,len);//维护
        }
    }
//选举最小节点
    private void maxHeapify(int[] nums,int i, int len) {
        //nums[i]为父亲节点
        int left = 2*i+1;
        int right = 2*i + 2;
        int minIndex = i;
        if(left < len && nums[left] < nums[minIndex]){
            minIndex = left;
        }
        if(right < len && nums[right] < nums[minIndex]){
            minIndex = right;
        }
        if(minIndex !=i) swap(nums, i, minIndex);
    }
//交换
    private void swap(int[] nums,int a,int b){
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}
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

实现堆排序

我们可以通过堆结构来实现排序，每次选择出极值后，“删除”极值再进行建堆即可。注意到上面的代码打印为2 4 5 6 9,这种情况只是偶然，堆并不是有序的，由其定义可知。

我们只需要在建堆的基础上在添加一个"删除"极值方法即可。通过交换最小下标节点和最大下标节点实现，因此，小根堆为降序排序，大根堆为升序排序。

 public void sort(int[] nums){
        int len = nums.length;
        buildMinHeap(nums,len);
        for(int i = len-1;i>=1;i--){
            swap(nums,i,0);
            len--;
            buildMinHeap(nums,len);
        }
    }

public class TestPriorityQueue {

    public static void main(String[] args) {
        int[] arr = {6,2,9,4,5};
        new Heap().sort(arr);
        for (int i : arr) {
            System.out.print(i);
        }
    }
    //96542
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21