学习参考：、

---

 

堆结构：一棵完全二叉树。大根堆：K[ i ] <  K[ 2i ] 、K[ i ] <  K[ 2i+1 ]  。小根堆反之。

本文测试数据：《严奶奶数据结构》P281

由于笔者学业繁忙，没有编写使树形结构可视化的代码。各位读者请心中脑补。

• 堆调整函数：

1      protected void HeapAdjust(int [] nums,int a,int b){ 2          int i; 3          for(i=a;a<=b;){ 4              //左子树=根*2+1，右子树=根*2+2 5              int lPos=a*2+1; 6              int rPos=(a+1)*2; 7              //比较找出左右子树最小的一颗 8              int min=nums[a];//根结点 9              int nextPos=lPos;//下一个转向的树10              boolean isSwaped=false;11              if(lPos<=b && nums[lPos]

函数描述：这个函数用于【建堆】、【筛选】两个操作。在这个函数中，对数组【a，b】中的元素进行处理，其认为除了“a”，在【a+1，b】中的元素都是满足{堆结构}的定义的。

1.求出左右子树的下标2.进行比较，在左右子树存在的情况下，获得值最小的子树（这个值最小的子树，它的值要比根节点的值小）3.如果没有这样的子树，跳出循环。　　有的话，转到子树进行操作，回到 1 进行循环。

• 建堆

1         //建堆2         for(i=len/2-1;i>=0;i--){3             HeapAdjust(nums,i,len-1);4         }

认为最下层的子树是规整（满足堆定义）的。通过从下层往上层调整，建立一棵满足堆定义的小根堆。

• 筛选

1         //筛选2         int ans[]=new int [len];3         for(i=0;i

1.拿出小根堆的根节点（最小），放入输出数组中

2.把最末尾的节点放入根节点。因为认为现在除了根节点，其他节点都是满足根定义的。所以对根节点使用【堆调整函数】

3.重复 1，直到拿走堆中所有的节点。

---

测试：

输入：49,38,65,97,76,13,27,49

输出：13 27 38 49 49 65 76 97 

 

完整java代码：

1 public class Main { 2  3     public static void main(String[] args) { 4         int []nums={49,38,65,97,76,13,27,49}; 5         HeapSort sort=new HeapSort(nums); 6         System.out.print(sort); 7     } 8  9 }10     11 class HeapSort{12     int [] sortAns;13     HeapSort(){}14     HeapSort(int[] nums){15         int i;16         int len=nums.length;17         //建堆18         for(i=len/2-1;i>=0;i--){19             HeapAdjust(nums,i,len-1);20         }21         //筛选22         int ans[]=new int [len];23         for(i=0;i