【数据结构与算法之排序与查找】堆排序

布满荆棘的人生 2024-03-25 16:38 69阅读 0赞

#### 【数据结构与算法之排序与查找】堆排序 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之排序与查找】堆排序
         *   *   *  1 大顶堆与小顶堆
                 *  2 堆排序
                 *   *  如何将原始序列调整为一个大顶堆

堆排序是一种特殊形式的选择排序，它是简单选择排序的一种改进。

###### 1 大顶堆与小顶堆 ######

具有n 个数据元素的序列 k 1 , k 2 , k 3 , . . . , k n \{k\_1,k\_2,k\_3,...,k\_n\} k1,k2,k3,...,kn ，当且仅当满足下面的关系时称为堆 Heap

*  大顶堆： k i ≥ k 2 i 且 k i ≥ k 2 i + 1 k\_i ≥ k\_\{2i\} 且 k\_i ≥ k\_\{2i+1\} ki≥k2i且ki≥k2i\+1
 *  小顶堆： k i ≤ k 2 i 且 k i ≤ k 2 i + 1 k\_i ≤ k\_\{2i\} 且 k\_i ≤ k\_\{2i+1\} ki≤k2i且ki≤k2i\+1

其中 $ i = 1,2,3,…, ⌊n / 2⌋$

> 我们下面讨论的堆排序问题都是基于大顶堆的

如果公式不好看，可以用一棵完全二叉树来表示堆序列，例如堆序列：\{49,22,40,20,18,36,6,12,17\} 可用下图所示的完全二叉树进行表示：

![在这里插入图片描述][248061f2ea3243778a4a5bb020db84b7.png_pic_center]

在大顶堆对应的完全二叉树中，根节点是最大值，并且二叉树中的每个节点的值均大于或等于其左右子树所有节点的值。

###### 2 堆排序 ######

利用堆的特性对序列进行排序：

*  从小到大排，用大顶堆
 *  从大到小排，用小顶堆

将一个包含n 个元素的序列进行堆排序(从小到大) 的过程如下：

1.  将原始序列调整为一个大顶堆
2.  交换大顶堆的第1个元素和最后一个元素，使第1个元素位于排序后的最终位置
3.  将尚未处于最终位置的前面的序列调整为一个大顶堆
4.  重复步骤2 一次和步骤3 (n - 1) 次

###### 如何将原始序列调整为一个大顶堆 ######

原始序列：\{49,22,40,20,18,36,6,12,17\}，原始完全二叉树

![在这里插入图片描述][1557da2ee7464fb5a53aed87495cf3b8.png_pic_center]

这是一个大顶堆，在进行堆排序时，步骤2，交换堆的第1个元素和最后一个元素

![在这里插入图片描述][4a9d69e3703e4be18cb73e202013e943.png_pic_center]

现在的序列就变成了 \{17,22,40,20,18,36,6,12,49\}，进行步骤3，将除节点49 外的其他节点 \{17,22,40,20,18,36,6,12\} 调整为一个大顶堆，去掉49 节点后的完全二叉

![在这里插入图片描述][7a34fe0b0c4a4b2292a2a05c4b89c48b.png_pic_center]

可以发现，除了17，其左右子树仍然满足大顶堆的性质。因此可以采用自上而下的办法将该完全二叉树重新调整为一个大顶堆。

具体操作方法：将序号为i 的节点与其左右孩子(序号分别为 2i 和 2i + 1)，这三个节点中的最大节点放到 i 的节点位置上，从上而下，彻底搞一次，这个完全二叉就会重新成为一个 【大顶堆】

调整第一次

![在这里插入图片描述][079559d89bb74bf297e1740468dcf9ef.png_pic_center]

OK，这样就完成了一趟堆排序。

\{49,22,40,20,18,36,6,12,17\} 这个序列的完整执行过程如下：

① \{17,22,40,20,18,36,6,12,**49**\}

![在这里插入图片描述][cf073b02f9144f9aa4a42b4b29dfd5ad.png_pic_center]

重新调整为大顶堆后

![在这里插入图片描述][41fcd47a4c014507ac4ea8d77f501984.png_pic_center]

调整后的序列：\{40,22,36,20,18,17,6,12,**49**\}

② \{40,22,36,20,18,17,6,12,**49**\}

交换第一个和待排序的最后一个

![在这里插入图片描述][3bd6c1730e1c4cccbed682d190c0ce32.png_pic_center]

\{12,22,36,20,18,17,6,**40,49**\}

重新调整为大顶堆

![在这里插入图片描述][248ebceff5d04049b7358d475af58ae0.png_pic_center]

调整后的序列变成： \{36,22,17,20,18,12,6,**40,49**\}，这样第二趟就完成了

③ \{36,22,17,20,18,12,6,**40,49**\}

交换第一个和待排序的最后一个

\{6,22,17,20,18,12，36,**40,49**\}

![在这里插入图片描述][df5ff90fe04a4210a297b6f66ecde165.png_pic_center]

\{6,22,17,20,18,12，**36,40,49**\}

将剩余序列重新调整为大顶堆

![在这里插入图片描述][a6c0b7722efb445da1e035788a3f5f5c.png_pic_center]

现在的序列：\{22，20,17,6,18,12，**36,40,49**\}

… 此处省略若干步骤

最终即可完成堆排序。

其实在算法的实际使用中，将尚未处于最终位置的序列再调整成一个大顶堆的过程并不需要在二叉树上进行，只是这样讲述更加清晰，实际上它只是将一个普通序列调整为堆的过程。

Java算法描述：

public void adjust(int[] k, int i, int n) {
        
        int j;
        int tmp;
        tmp = k[i - 1];
    
        j = 2 * i;
        while (j <= n) {
        
            if (j < n && k[j - 1] < k[j]) {
        
                j++; // j为左右孩子中较大孩子的序号
            }
            if (tmp >= k[j - 1]) {
        
                break; // tmp为最大的元素，不需要交换
            }
            k[j / 2 - 1] = k[j - 1];  // 交换元素
            j = 2 * j;
        }
        k[j / 2 - 1] = tmp; // 将k 中第i个元素放在调整后的最终位置上
    }

这个函数的作用是将序列 k 中以第i 个元素为根节点的子树调整为一个大顶堆。

【注意】调用这个函数的前提是该子树中除了根节点，其余子树都符合堆的特性。

【举个栗子】

原始序列：\{23,6,77,2,60,10,58,16,48,20\} 对应的完全二叉树如下：

![在这里插入图片描述][34e84227858142149471049d1617682f.png_pic_center]

如果原序列对应的完全二叉树有 n 个节点，那么从第 ⌊n / 2⌋ 个节点开始，即初始时 i = ⌊n / 2⌋，调用函数 adjust() 进行调整，每调整一次后 执行 i = i - 1，直到i = 1时，再调整一次，就可以把原序列调整为一个堆。

这个栗子中，一共10 个节点，所以i 从5开始，

调整完第5个节点：

![在这里插入图片描述][47aa7919146645bfb5eac3a80922be22.png_pic_center]

调整完第4个节点：

![在这里插入图片描述][1fcdb91dc9b2496f84fbb5b6dad1ebf2.png_pic_center]

调整完第3个节点：

![在这里插入图片描述][276d189bc8594dc2ab8be5b307a48f5d.png_pic_center]

调整完第2个节点：

![在这里插入图片描述][c5acdf7d13f44e64b79431ee0928d0e4.png_pic_center]

调整完第1个节点：

![在这里插入图片描述][a3df6aa4992e408fb2ab7935ecfccbda.png_pic_center]

再将原始序列调整为一个大顶堆后就可以进行堆排序了。

堆排序的算法Java 描述如下：

public static void heapSort(int[] array) {
        
        int i;
        int tmp;
        for (i = array.length / 2; i >= 1; i--) {
         // 将原始序列初始化为一个堆
            adjust(array, i, array.length);
        }
    
        // 交换第1个和第n个元素，再将根节点向下调整
        for (i = array.length - 1; i >= 0; i--) {
        
            tmp = array[i];
            array[i] = array[0];
            array[0] = tmp;
            adjust(array, 1, i);  // 将根节点向下调整
        }
    }

测试

public static void main(String[] args) {
        
    
        int[] array = {
        3, 12, 20, 1, 0, 5, 8, 19, 5};
        heapSort(array);
    
        for (int e : array) {
        
            System.out.print(e + " ");
        }
    
    }

运行结果

![在这里插入图片描述][ea0ecf16e2d7498c8e0e762ba4df7adf.png_pic_center]

[248061f2ea3243778a4a5bb020db84b7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9573be1c96d445699f5240099dcd4e3b.png
[1557da2ee7464fb5a53aed87495cf3b8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f00545edf216466198329a9b9952ccc3.png
[4a9d69e3703e4be18cb73e202013e943.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/712b9620282844e0b4eb0835beb87d89.png
[7a34fe0b0c4a4b2292a2a05c4b89c48b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b3e1bb34f1dc4fd9ba1ded593e5d41f7.png
[079559d89bb74bf297e1740468dcf9ef.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c15e9ce35d5a46f2b241c7dd4f737589.png
[cf073b02f9144f9aa4a42b4b29dfd5ad.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/384b34f1a5c24619b760d3637901f056.png
[41fcd47a4c014507ac4ea8d77f501984.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d567896f3a584421a7e61dba6a450211.png
[3bd6c1730e1c4cccbed682d190c0ce32.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1c98a158b01644cca748eeeb667ab744.png
[248ebceff5d04049b7358d475af58ae0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/82187888143a4dbcb54658fa4d5e4fa8.png
[df5ff90fe04a4210a297b6f66ecde165.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d719569f9c224daf8c1174b170e85a31.png
[a6c0b7722efb445da1e035788a3f5f5c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/87b410d92d4b4252be221550b52807d0.png
[34e84227858142149471049d1617682f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2ad4ca1dc7a74dcc828c470b040412f5.png
[47aa7919146645bfb5eac3a80922be22.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9116bfa6ef9942caabf97ac9b9b3a878.png
[1fcdb91dc9b2496f84fbb5b6dad1ebf2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/89bde5670b5e44eca9863da6cc324aa5.png
[276d189bc8594dc2ab8be5b307a48f5d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/30ff813c8ed54c37b8e8e400b2a12a3c.png
[c5acdf7d13f44e64b79431ee0928d0e4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/6c1c974a53e742a7a7af64dbd4fdd3cf.png
[a3df6aa4992e408fb2ab7935ecfccbda.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2151a62539a14ba4aeddf9321bc959d4.png
[ea0ecf16e2d7498c8e0e762ba4df7adf.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d8041c3005524d9faf0c7b1a24bb4cf7.png