堆排序

前言堆（二叉堆）是一种用于实现优先队列模型的数据结构，堆具有堆序（heap order）性，每个节点的关键字都大于他的父节点的只有根除外（没有父亲），也可以是都小于，子节点与父节点的关系决定了这个堆是最小堆还是最大堆，分别可以用来做升序和降序。使用优先队列理论上可以实现花费O(N log N)时间的排序。 方法对一个数组进行升序的排列，可以先将数组中的N个元素建立一个二叉堆，这个操作花费O(N)时间，然后对该堆执行N此DeleteMin操作。堆中的数据按照从小到大依次离开堆，将这些元素记录到第二个数组中，最后再拷贝回来，以此得到了针对N个元素的排序。每个DeleteMin操作花费了O(log N)的时间，因此总开销是O(N log N)。注意到我们这里使用了一个额外的数组，空间开销加大了（将第二个数组数据拷贝回来只花费O(N)，不会显著增加时间消耗）。虽然我们在程序中常常为了节省时间开销而消耗额外的空间，但在这个问题中有个方法可以避免。在每次DeleteMin操作之后，堆缩小了1，，因此堆中最后的单元可以用来存放刚刚删去的元素。 DeleteMin（删除最小元）这是在排序中重点需要的基本堆操作，要找到需要删除的元素很容易，难的是删除，当删除一个最小元时，在根节点产生了一个空穴，为了保证堆的性质，必需将堆中最后一个元素X移动，如果它可以移动到空穴，那么DeleteMin完成，不过这一般不太可能，因此我们将空穴的两个子节点中较小的一个移入空穴，相当于把空穴往下移动了一层，不断重复这个过程直到X可以被放到空穴。这种策略被称作下滤。最小堆与最大堆具有对称的性质，对于父节点大于子节点的最大堆，区别只是每次删除的是最大元，上移的是空穴子节点中较大的，与最小堆相反。 图片演示 代码#define LeftChild(i) (2 * (i) + 1)void PercDown(ElementType A[], int i, int N) { int Child; ElementType Tmp; for (Tmp = A[i]; LeftChild(i) < N; i = Child) { Child = LeftChild(i); if (Child != N - 1 && A[Child + 1] > A[Child]) Child++; if (Tmp < A[Child]) A[i] = A[Child]; else break; } A[i] = Tmp;}void Heapsort(ElementType A[], int N) { int i; for (i = N / 2; i >= 0; i--) PercDown(A, i, N); for (i = N - 1; i > 0; i--) { Swap(&A[0], &A[i]); PercDown(A, 0, i); }}

定义堆是一种特别的树状结构，我们首先来看看维基百科的上定义。堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于） C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。总结来说，堆是一个完全二叉树，最多只有两个子节点，并且必须保证根节点是最大的值或者最小的值，所以对于一个堆而言，根节点是最大的值或者是最小的值。存储因为堆是一棵完全二叉树，所以使用数组可以高效的存储数据。对于使用数组存储的方式，有两个性质非常关键，对于一个非根节点的节点i来说，如果它的下标为k，那么它的父节点的下标为 (k -1)/2，子节点的下标为2 *k +1和2 *k + 2基本操作堆化插入删除堆化对于任意一个无序数组而言，实现堆化的步骤如下，我们以构建一个最大堆为例：找到第一个非叶子节点，对这个节点的左子树和右子树与节点比较，将大的元素放置到父节点的位置，直到父节点已经是最大值或者改节点已经是叶子节点。依次对所有的非叶子节点进行第一步的操作private Heap(int[] data){ int last_p = data.length - 1; //i是第一个非叶子节点 for (int i = (last_p - 1) / 2; i >= 0; i–) { heapify(data, i, last_p); } this.data = data;}private void heapify(int[] data, int start, int end){ int value = data[start]; int current_p = start; //左孩子 int left_p = 2 * current_p + 1; while (left_p <= end) { //右节点大于左节点 if (left_p < end && data[left_p] < data[left_p + 1]) { //移动位置到右节点 left_p++; } //当前的父节点已经是最大值 if (data[left_p] < value) { break; } else { //子节点上移到父节点的位置 data[current_p] = data[left_p]; current_p = left_p; left_p = current_p * 2 + 1; } } data[current_p] = value;}插入插入的算法如下：.将新增的节点放在数组的最末端，也就是数组的最后一个位置。然后计算出父节点的位置，让当前节点与父节点比较，如果父节点比较小，交换位置。重复上述步骤，直到父节点大于当前节点或者当前节点是根节点。public int insert(int value){ checkSize(); int position = data.length - 1; data[position] = value; int current_p = position; int parent_p = (position - 1) / 2; while (current_p > 0) { if (data[parent_p] > value) { break; } else { data[current_p] = data[parent_p]; current_p = parent_p; parent_p = (current_p - 1) / 2; } } data[current_p] = value; return position;}删除删除的算法如下：将数组最后一个节点与当前需要删除的节点替换，删除最后一个节点，对于替换的节点来说，相当于进行了依次插入操作，不过这次是从上往下的插入。算法与remove相同，也是比较最大的值进行替换，直到不满足条件为止。删除根节点public int remove(){ int root = data[0]; int last = data[data.length - 1]; data[0] = last; data = Arrays.copyOf(data, data.length - 1); if (data.length == 0) { return root; } //从顶点开始调整 int current_p = 0; int l = current_p * 2 + 1; int value = data[current_p]; while (l < data.length) { if (l < data.length - 1 && data[l] < data[l + 1]) { l++; //右孩子大 } if (data[l] <= value) { break; } else { data[current_p] = data[l]; current_p = l; l = current_p * 2 + 1; } } data[current_p] = value; return root;}应用堆应用比较多的一个用处就是堆排序，对于一个数组进行堆化之后，第一个数组是最大的值，然后交换第一个数和最后一个数，这样最大的数就落在了最后一个数组的位置。缩小数组，重复之前的步骤，最后就得到了一个排序好的数组。int[] data = new int[] {20, 40, 80, 33, 111, 47, 21, 90, -1};HeapSort hs = new HeapSort();hs.heap_array(data, data.length - 1);for (int i = 0; i < data.length - 1; i++){ int tmp = data[0]; data[0] = data[data.length - 1 - i]; data[data.length - 1 - i] = tmp; hs.heap_array(data, data.length - 2 - i);}System.out.println(Arrays.toString(data));代码地址： https://gitee.com/devnew/Algo… ...

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。且完全二叉树可以基于数组存储（父子节点的关系可以用数组下标表示），加持上堆的特性，故可以做堆排序。满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树；即每一层节点数都达到最大值；即深度为 k 的二叉树节点个数为 2^k-1，则为满二叉树；完全二叉树：若设二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，且第 k 层所有的结点都连续集中在最左边，这就是完全二叉树。堆：基于完全二叉树，分为大顶堆/小顶堆。各节点的数值皆大于其左右子节点的数值（大顶堆），或各节点的数值皆小于其左右子节点的数值（小顶堆）堆的特性大顶堆，节点的数值皆大于子节点的数值，下文都以大顶堆为实例讲解。因为是基于完全二叉树的，所以堆还有一些相应的特性：1、位序为 n 的节点，其父节点位序为 (int) n/22、位序为 n 的节点，其左子节点位序为 2n，右子节点位序为 2n+1（这是按照位序从1开始计算，但对编程语言不太友好，如果位序从0开始计算，则左子节点位序为 2n+1, 右子节点位序为 2n+2）按照数组下标的方式去编号的话如下： 0 / \ 1 2 / \ / \ 3 4 5 6 … / floor(n/2) … / n / \2n+1 2n+2可以发现，所有非叶子节点的序号都会落在 0 ~ (int) N/2-1 区间中，N为节点总数，例如：1、有4个节点，节点编号为03，非叶子节点编号区间值为 01，即编号为 0，1 的节点为非叶子节点。2、有5个节点，节点编号为04，非叶子节点编号区间值为 01，即编号为 0，1 的节点为非叶子节点。3、有6个节点，节点编号为05，非叶子节点编号区间值为 02，即编号为 0，1，2 的节点为非叶子节点。4、有7个节点，节点编号为06，非叶子节点编号区间值为 02，即编号为 0，1，2 的节点为非叶子节点。可以很方便的获取完全二叉树的非叶子节点的序号集合，从 k-1 层开始，依次将各非叶子节点及其左右子节点视为一个完全二叉树，将其调整至大顶堆，直至根节点，这时整个二叉树就是一个大顶堆我们有了非叶子节点的序号及获取左右节点序号的算式，所以很容易就可以将各非叶子节点及其左右子节点组成的完全二叉树调整至大顶堆。同时要注意如果非叶子节点同其左右子节点发生了调整，其左右子节点如果也是非叶子节点的话，也要检测是否破坏了堆特性，如破坏也需进行调整。堆排序堆排序：将初始待排序关键字序列(R0,R1….Rn-1)构建成大顶堆，此堆为初始的无序区将堆顶元素R[0]与最后一个元素R[n-1]交换，此时得到新的无序区(R0,R1,…,Rn-2)和新的有序区(Rn-1),且满足R[1,2…n-2]<=R[n-1]由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R1,…,Rn-2)调整为新堆，然后再次将R[0]与无序区最后一个元素交换，得到新的无序区(R0,R1….Rn-3)和新的有序区(Rn-2,Rn-1)。不断重复此过程直到有序区的元素个数为n-1（第n-1次调整时完全二叉树只有2个节点，即可有序化），则整个排序过程完成。即堆排序的过程:将待排序数组映射到完全二叉树中，通过调整完全二叉树至大顶堆，获取根节点的值（节点最大值）。那大顶堆的构建如何做呢？我用比较白话的方式讲一下1、从 k 层开始，将每一层子节点的最大值与其父节点的值进行比较调整（如发生交换且子节点为非叶子节点，也要检查子节点的树是否满足了父节点大于子节点的特性）2、重复第一步骤直到根节点，此时根节点的值即为完全二叉树节点中的最大值，即生成了大顶堆源码实例package mainimport ( “fmt”)func main() { // 待排序数组 go 的数组传参是值拷贝 我们用切片引用传值更方便些 var arr = []int{1, 6, 2, 4, 5, 3, 7, 9, 8} HeapSort(arr) fmt.Print(arr)}// 堆排序func HeapSort(arr []int) { arrLength := len(arr) // 每一次的堆构建都能得到一个节点中的最大值（根节点）对于N个待排序数列，N-1次堆构建即可得出有序数列 for i := 0; i < arrLength; i++ { // 无序区长度 arrLengthUnsorted := arrLength - i // 无序区构建为完全二叉树后非叶节点的下标的范围 unLeafNodeIndexRange := int(arrLengthUnsorted/2 - 1) // 从 k - 1 层开始 将非叶节点的子树分治递归构建成大顶堆 for j := unLeafNodeIndexRange; j >= 0; j– { HeapBuild(arr, j, arrLengthUnsorted) } // 打印下标 0 ~ arrLengthUnsorted-1 的数列 fmt.Println(“current heap: “, arr[0:arrLengthUnsorted]) // 一次大顶堆构建完成，根节点为堆最大值，与无序区堆的最后一个节点交换 // 无序区节点数-1 // 破坏了堆结构 开始对新无序区做大顶堆构建 SwapItemOfArray(arr, 0, arrLengthUnsorted-1) }}// 将子树调整为大顶堆func HeapBuild(arr []int, nodeIndex int, arrLengthUnsorted int) { // 完全二叉树子节点下标同父节点下标的关系式 leftChildNodeIndex, rightChildNodeIndex := nodeIndex2+1, nodeIndex2+2 // 防止子节点下标越界 && 子节点数值大于父节点 则交换节点值 if leftChildNodeIndex < arrLengthUnsorted && arr[leftChildNodeIndex] > arr[nodeIndex] { SwapItemOfArray(arr, leftChildNodeIndex, nodeIndex) HeapBuild(arr, leftChildNodeIndex, arrLengthUnsorted) //左子树根节点改变 需调整堆结构 } if rightChildNodeIndex < arrLengthUnsorted && arr[rightChildNodeIndex] > arr[nodeIndex] { SwapItemOfArray(arr, rightChildNodeIndex, nodeIndex) HeapBuild(arr, rightChildNodeIndex, arrLengthUnsorted) //右子树根节点改变 需调整堆结构 }}// 交换数组两个元素func SwapItemOfArray(arr []int, indexX int, indexY int) { temp := arr[indexX] arr[indexX] = arr[indexY] arr[indexY] = temp} ...