【面试知识点】史上最全面讲解----堆排序

不念不忘少年蓝@ 2023-03-01 11:41 1阅读 0赞

# 引言 #

> ☞梦想进大厂的一只程序猿☜
> 
> ☞期望毕业前力扣刷够400题☜
> 
> ☞正在复习数据结构和算法☜

## [【2020秋招-面试题目汇总（随时更新）】][2020_-] ##

# 堆排序的过程 #

## 堆父节点和子节点 ##

*  1.  parent(3) = (i - 1) / 2;
    2.  c1(5) = 2 \* i + 1;
    3.  c2(6) = 2 \* i + 2;

## 建立大顶推和小顶推 ##

建堆的过程，我们需要知道一个函数heapify()【这里的heapify不代表最终版本】

public static void heapify(int[] tree, int n, int i) {
                if (i >= n) {
    			return;
    		}
    		int max = i;
    		int c1 = 2 * i + 1;
    		int c2 = 2 * i + 2;
    		if (c1 < n && tree[c1] > tree[max]) {
    			max = c1;
    		}
    		if (c2 < n && tree[c2] > tree[max]) {
    			max = c2;
    		}
    		if (max != i) {
    			duiSwap(tree, max, i);
    		}
    	}

这个函数用来进行3、5、6中，将最大的数与3交换

![20200724165547101.png][]

我们对于每一个结点利用heapify，这样，我们是否就得到了一个完整的堆？

我们往下看看，当3与6交换完后，我们再对结点2进行heapify()，2与7进行交换，然后对结点4进行heapify，6与4进行交换，最后1与7交换，我们看看最后的结果

![20200724165612319.png][]

我们考虑下，关于堆的定义：是一个完全二叉树、父节点全部大于等于或者全部小于等于子节点

我们看下图，可以看出明明5和3是4的子节点，为什么4还小于6呢？

同理，5和2也是1的子节点，为什么1还小于5呢？

![20200724165627101.png][]

这说明了我们对于堆的建立出现了错误，难道是我们的heapify出现了错误，我们从头开始分析一下：

![2020072416564787.png][]

首先，当我们将3和6进行交换时，这时候我们仅仅改变的是3-5-6之间的关系，也就是合理的，继而我们以2为父节点，改变2-5-7之间的关系，也是合理的，

![2020072416570898.png][]

当我们对以节点4进行heapify时，我们会将6和4的位置进行调换

![20200724165728388.png][]

这时候，聪明的你有没有看出什么错误导致的我们的建堆错误？

答案是：当我们对结点4进行heapify时，将4转变至子节点，破坏了下面这个小堆

![20200724165841697.png][]

也就是，对于交换后，我们原来排序好的堆，就失去了稳定性，有什么办法能让我们原来排序的堆也是顺序的嘛？

聪明的你可能想到了，我们再一次进行heapify不就可以了，对，我们只需要对交换完之后的节点再一次使用heapify，也就是对于上图中进行heapify，得到如下

![20200724165906409.png][]

![20200724165918757.png][]

按照上面的想法，我们对节点1再一次进行heapify

这时候聪明的你，能不能想到我们的heapify少了点什么？

对，我们一开始的heapify少了对改变的子节点进行heapify，我们怎么实现呢？

这里只需要递归就可以了，也就是对改变的子节点进行heapify

public static void heapify(int[] tree, int n, int i) {
    		if (i >= n) {
    			return;
    		}
    		int max = i;
    		int c1 = 2 * i + 1;
    		int c2 = 2 * i + 2;
    		if (c1 < n && tree[c1] > tree[max]) {
    			max = c1;
    		}
    		if (c2 < n && tree[c2] > tree[max]) {
    			max = c2;
    		}
    		if (max != i) {
    			duiSwap(tree, max, i);
    			heapify(tree, n, max);
    		}
    	}

这时候我们的堆就建好了，我们可以进行下一步操作，堆排序

## 进行堆排序 ##

对于堆排序，我们使用方法是：

每次将root与末尾的进行交换，然后对root进行heapify

我们看一下图示：

![20200724170006242.png][]

![20200724170028636.png][]

依次进行这种操作，我们最后得到的数组就是从小到大排序好的

**注意：我们进行堆排序的时候，我们每次重新对节点使用heapify时，我们已经排序好了一个7，所以下一次进行heapify时，n(也就是heapify的范围)就可以直接除去一个7，后面也是这样**

# 源代码 #

public static void duiSwap(int[] tree, int i, int j) {
    		int x = tree[i];
    		tree[i] = tree[j];
    		tree[j] = x;
    	}
    
    	public static void heapify(int[] tree, int n, int i) {
                if (i >= n) {
    			return;
    		}
    		int max = i;
    		int c1 = 2 * i + 1;
    		int c2 = 2 * i + 2;
    		if (c1 < n && tree[c1] > tree[max]) {
    			max = c1;
    		}
    		if (c2 < n && tree[c2] > tree[max]) {
    			max = c2;
    		}
    		if (max != i) {
    			duiSwap(tree, max, i);
    			heapify(tree, n, max);
    		}
    	}
    
    	public static void bulidDui(int[] tree, int n) {
    		int last = n - 1;
    		int parent = (last - 1) / 2;
    		for (int i = parent; i >= 0; i--) {
    			heapify(tree, n, i);
    		}
    	}
    
    	public static void duiSort(int[] tree, int n) {
    		bulidDui(tree, n);
    		for (int i = n - 1; i >= 0; i--) {
    			duiSwap(tree, i, 0);
    			heapify(tree, i, 0);
    		}
    	}
    
    	public static void main(String[] args) {
    		int[] tree = new int[] { 2, 5, 3, 1, 10 };
    		int n = tree.length;
    		duiSort(tree, n);
    		for (int i = 0; i < n; i++) {
    			System.out.println(tree[i]);
    		}
    	}

[2020_-]: https://blog.csdn.net/qq_40915439/article/details/107908926
[20200724165547101.png]: /images/20230208/6b73fbf4fb374f679da573ec839c2e10.png
[20200724165612319.png]: /images/20230208/9d5bda1fcc1945279e5484c465256bb5.png
[20200724165627101.png]: /images/20230208/568f6aeeae544d60b10a23cde0ba4ad5.png
[2020072416564787.png]: /images/20230208/fffffd664bca470eadb66a4c893ea2aa.png
[2020072416570898.png]: /images/20230208/bc247a378d90463eac8d3990a9d7bb8f.png
[20200724165728388.png]: /images/20230208/8828a7e55e2f4096ab958671290676f2.png
[20200724165841697.png]: /images/20230208/4e38bc92cb534e3ca5e8a8a722ae81df.png
[20200724165906409.png]: /images/20230208/79f979d21a144107bfc2c80a5ee6eefc.png
[20200724165918757.png]: /images/20230208/c479f6fd8d3e401faf12a1e8eff01b99.png
[20200724170006242.png]: https://img-blog.csdnimg.cn/20200724170006242.png
[20200724170028636.png]: https://img-blog.csdnimg.cn/20200724170028636.png