一、堆的定义
堆的数据结构是一个数组，对于数组中任意节点i，其值小于节点2i和2i+1的值，则称该数组是一个小顶堆。
二、建堆注意事项
1、数组从下标1开始存放数据，可以简化程序逻辑，i/2即是i的父亲节点。
2、建堆时，从最末叶子节点开始往前遍历，调整每个节点所在的子树，使其满足堆的定义，由于叶子节点本身肯定满足堆定义，实际只需要从最末叶子节点的父亲节点开始即可。
三、调整堆
1、对于根、左子树、右子树而言，如果根比其中一个子树节点小，则将根与子树中最小的节点交换。交换之后有可能导致被交换的子树不符合堆定义，需要递归的进行调整，直到叶子节点或者某次比较没有节点交换，即完成调整。
四、堆排序
堆排序的过程如下：
1、建堆：n/2*logn
2、取堆顶作为排序结果的第一个元素，将最末叶子节点换到根节点，重新调整堆，使其满足定义；
3、重复步骤2，直到堆中没有元素。
目录 1.堆排序介绍 2.堆排序图文说明 3.堆排序的时间复杂度和稳定性 4.堆排序实现 堆排序介绍 堆排序(He...
本文主要介绍堆排序的一些基本过程和分析。 大纲 堆排序简介 堆排序代码实现 1. 堆排序简介 1.1 堆排序的存储...
最小K个数 堆排序 堆排序
原理 堆排序原理 实现 说明 堆排序对大文件很有效 堆排序是不稳定排序
iOS算法总结-堆排序 iOS算法总结-堆排序
转载：图解排序算法(三)之堆排序 预备知识 堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选...
原创 堆排序： 使用visit数组从本质出发获取大顶堆排序。
堆排序
整段源码链接C++的模板元堆排序 要点 组建数据结构list 组建对list的各种基本操作 堆排序中组建堆排序个个...
参考链接 选择排序：堆排序（Heap Sort） 白话经典算法系列之七 堆与堆排序 堆排序与快速排序，归并排序一样...
本文标题：堆排序
本文链接：https://www.haomeiwen.com/subject/xtfivttx.html
网友评论