堆排序代码解析 堆排序的算法及代码实现

目前这个系列的文章都选择了非常经典和抢眼的算法，今天的堆排序算法就是其中之一。首先，明白什么是堆。堆不是程序中的内存区域，而是用完整的二叉树表示的数据结构。堆具有以下

目前这个系列的文章都选择了非常经典和抢眼的算法，今天的堆排序算法就是其中之一。首先，明白什么是堆。堆不是程序中的内存区域，而是用完整的二叉树表示的数据结构。堆具有以下特征

是一个完全二叉树堆的每个节点的值必须大于等于左右树节点（大顶堆），或小于等于左右树节点（小顶堆）。

简单来说，完全二叉树是指除了最后一个叶节点之外的所有节点都有两个子树，叶节点可以没有子树，也可以只有左子树。下图是一个大顶桩:

小顶堆小丁堆

许多

因为堆是完全的二叉树，所以非常适合数组存储。上图是大顶堆的存储情况，这里不使用a[0]，a[1]是大顶堆的顶点，也就是最大的数据，a这是另一个窍门。删除顶部元素时，不能直接删除。你应该把最上面的元素和最后一个元素交换，然后根据堆的特点调整堆，直到满足条件。= 7是左边子树的顶点，a[12+1]= 6是右边子树的顶点，其他节点以此类推。

使用图表显示以下内容:

在堆中插入一个元素，先插入到最后一个数组元素位置，然后和自己的父节点6比较。因为大于6，不符合大顶堆的条件，所以9和6互换，然后9和顶元素8比较，但是不符合大顶堆的条件。继续交换，最后形成大顶堆。这一步叫做堆积。

对于大顶堆，堆顶部的元素是最大的。如果依次删除堆顶的元素并输出，那么数字由大到小排列。

[12]

完整的代码如下:

package com.dianneng.lms;public class TestHeap { private int [] a; private int n; private int count; public TestHeap(int cap) { a = new int[cap+1]; n = cap; count = 0; } public void swap(int i,int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; return; } public void print(){ for (int i = 0; i <= count;i++) { System.out.print(a[i]+"t"); } } public int insert( int v) { if (count == n) { System.out.println("Heap is full!"); return -1; }else { a[++count] = v; int i = count; while (i/2 >0 && a[i] > a[i/2]) { swap(i,i/2); i = i/2; } } return 0; } public int removeMax() { if (count == 0) { return -1; } System.out.print(a[1]+"t"); a[1] = a[count]; --count; heapify(count,1); return 0; } private void heapify(int n, int i) { while(true) { int maxPos = i; //通过左右子树顶点比较获得最大数节点 if (i*2 <= n && a[i] <a[i*2] ){ maxPos = i*2; } if (i*2+1 <= n && a[maxPos] < a[i*2+1]) { maxPos = i*2+1; } //已经是最大的不用交换了 if (maxPos == i) { break; } //需要交换 swap(i,maxPos); //i指向待交换的 i = maxPos; } } public static void main(String [] args) { TestHeap th = new TestHeap(18); th.insert(8); th.insert(7); th.insert(6); th.insert(5); th.insert(4); th.insert(3); th.print(); System.out.println(); while(th.removeMax() == 0) { } }}

可以利用大顶堆的特点，先对数组进行排序，然后依次交换顶元素和最后一个元素，再对堆进行堆栈，将堆的大小减一。最后，输出的是从小到大排序的数组。借用老师的一张图来表示: