一、二叉堆简介：
二叉堆是一个完全二叉树或者是近似完全二叉树。
堆分为最大堆和最小堆，最大堆的任意非叶结点的关键字不小于其左右孩子结点的关键字，最小堆反之。
二、二叉堆的特点：
若其结点的编号为[0,n-1]，其中n为结点的个数，若当前结点的编号为i，则其左孩子结点的编号为2i+1，其右孩子的编号为2i+2,其父结点的编号为(i-1)/2；
若其结点的编号为[0,n-1]，则其(n-1)/2+1,到n-1这些编号的结点都是叶子结点；
利用最小堆来进行降序排序，利用最大堆来进行升序排序。
三、堆排序的思想:
构造最小堆：初始待排序的序列构建成一个最小堆，此堆为初始的无序区；从二叉堆的最后一个非叶子结点开始调整，每次调整都是从父结点、左孩子结点，右孩子结点三者中选择最小者和父结点进行交换（交换之后可能造成被交换的孩子结点不满足二叉堆的性质，因此每次交换之后要重新对被交换的孩子结点进行调整）。
交换元素：将堆顶元素与最后一个元素进行交换，得到一个新的无序区和新的有序区，且满足无序区的数据不小于有序区的元素；调整堆：由于交换后新的堆顶不满足堆的性质，因此需要对当前无序区调整为新堆，
将无序区的堆顶元素与无序区的最后一个元素进行交换，得到新的无序区和有序区，再对当前无序区调整为新堆，不断重复步骤2和3，直到有序区包含n-1个元素，即结束排序。
四、空间复杂度：堆排序每次只对一个元素进行操作，是就地排序的，其空间复杂度为O(1);
五、时间复杂度：O(N*lgN)；
六、稳定性：不稳定；堆排序在交换数据的时候，是比较父结点和子结点之间的数据，所以即使存在2个数值相等的兄弟结点，他们的相对顺序在排序中也可能发生变化。
（算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！）
七、最好情况和最坏情况：待补充；
八、java代码实现
package cq.sortAlgorithm.com;
import org.junit.Test;
public class HeapSort { //建立最小堆 public static void BulidMinHeap(int[] array) { int n = array.length-1; for(int i =(n-1)/2;i>=0;i--) { //HeapSort.partMinHeap(array, i, n); HeapSort.MinHeapFixDown(array, i, n); } for(int data:array) System.out.print(data+" "); } //结点区间为[0,n-1],即从结点i=(n-1)/2开始进行调整， //结点i的右子节点为2i+1,左子节点为2i+2; /** * 该代码只下沉一次 * @param array * @param i * @param n */ public static void partMinHeap(int[] array,int i,int n) { int temp; temp = array[i]; int j =2*i+1; if(j <= n) { if(j+1<= n && array[j]>array[j+1]) { j++; } if(array[j] <temp) { array[i]=array[j]; array[j] =temp; } } } /** * 当前结点i进行下沉 * @param array :数据源 * @param i :当前节点的编号 * @param n :最后一个节点的编号 */ public static void MinHeapFixDown(int[] array,int i,int n) { int j = 0; int temp =0; j = 2*i+1; temp = array[i]; while(j<=n) { if(j+1<= n && array[j]>array[j+1]) { j++; } if(array[j] >= temp) { break; } array[i] =array[j]; i = j; j =2*i +1; } array[i] = temp; }
public static void MinHeapFixUp(int[] array,int i) { int j,temp; j = (i-1)/2; temp = array[i]; while(i!= 0 && j>= 0) { if(array[j] <= temp) { break; } //将父结点往下移 array[i] =array[j]; i = j; j =(i-1)/2; } array[i] =temp; } //堆的删除 ,删除堆顶元素array[0] public static void MinHeapDel(int[] array,int n) { int temp = array[n]; array[n] =array[0]; array[0] = temp; HeapSort.MinHeapFixDown(array, 0, n-1); for(int data:array) System.out.print(data+" "); } //堆的插入 public static void MinHeapAdd(int[] array) { HeapSort.MinHeapFixUp(array,array.length-1); for(int data:array) System.out.print(data+" "); } //@Test public void test() { int[] array ={3,3,8,12,32,4,5,18,23}; HeapSort.BulidMinHeap(array); //构建最小堆 System.out.println(); HeapSort.MinHeapDel(array,array.length-1);//删除堆顶元素 System.out.println(); array[array.length-1] = 16;//添加一个元素 HeapSort.MinHeapAdd(array); } @Test public void MinHeapSort() { int[] array = {12,3,2,15,2,8,18,2,45}; //构建最小堆 HeapSort.BulidMinHeap(array); for(int i = array.length-1;i>0;i--) { //交换数据 int temp = array[i]; array[i] = array[0]; array[0] = temp; //调整数据 HeapSort.MinHeapFixDown(array, 0, i-1); } System.out.println(); for(int data:array) System.out.print(data+" "); } }
九、参考图片
