HeapSort

转载自：链接：https://www.jianshu.com/p/719b0de606a7 作者：Geek5Nan

侵删

主要内容概述

• 什么是二叉堆

• 二叉堆的有序化

  • 当子节点 > 父节点

  • 当父节点 > 子节点

• 二叉堆实现优先队列(priority queue)

• HeapSort的实现

什么是二叉堆

一、当二叉树满足满足如下条件时，我们说这个二叉树是堆有序的：

1. 每一个父结点的值都比它的子结点大（称为大顶堆）或小（称为小顶堆）
2. 子结点的大小与其左右位置无关

二、二叉堆的两种实现方式

1. 堆有序的二叉树，也可称为二叉堆。

2. 二叉堆是最常见的堆结构，因此也常将二叉堆直接称为堆，可以采用如下两种方式来表示二叉堆

   • 使用指针

     • 二叉树的每个结点需存储三个指针，分别指向其父结点和两个子结点

   • 使用数组

     a. indices start at 1 下标从1开始
     b. Take nodes in level order（层序遍历）
     c. parent of node at k is at k/2
     d. children of node at k are 2k and 2k+1

3. 堆的数组表示

   image

二叉堆的有序化

• 以大顶堆为例，有序化的过程中我们会遇到两种情况

  • 在堆底加入一个较大元素时，我们需要由下至上恢复堆的顺序

  • 当将根结点替换为一个较小元素时，我们需要由上到下恢复堆的顺序

1. 由下至上的堆有序化（上浮-swim）

• 条件：

  • 堆的有序状态因为某个结点变的比它的父结点更大而被打破
  • 即出现子节点大于父节点的情况（violation ：子节点）

• 解决方法(Eliminate the violation)

  • Exchange key in child with key in parent(将它与它的父结点交换来恢复堆有序)

  • repeat until heap order restored (交换后，这个结点比它的两个子结点都大，但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍的用同样的方式来将其向上移动，直到遇到一个比它更大的父结点或到达了堆的根结点)

• 实现代码

    public static void swim(int k){
    
        while(k > 1 && less(k/2,k)){
        
            exch(k/2,k);
  
            k = k/2;    
        }
    }
  

• 图示

  image

• 实现在堆中插入(Insertion in a heap)

  • Add node at end, then swim it up

      public void insert(Key k){                  //Key类型实现Comparable接口
      
          pq[++N] = k;                            //插入到最后
    
          swim(N);                                //上浮
      }
    

2. 由上至下的堆有序化（下沉-sink）

• 条件

  • 堆的有序状态因为某个结点变的比它的某个子结点更小而被打破

  • 即出现父节点小于子节点的情况(violation : 父节点)

• 解决方法(Eliminate the violation)

  • Exchange key in parent with key in larger child(将它和它的子结点中较大者交换位置来恢复堆有序)

  • Repeat until heap order restored(交换可能会在子结点处继续打破堆的有序状态，此时可以采用相同的方式，将结点向下移动直到它的子结点都比它小或是到达了堆的底部)

• 实现代码

    public void sink(int k){
        
        while(2 * k <= N){
            int j = 2 * k;
            
            if(j < N && less(j,j+1)) j++;       //j指向较大子节点
  
            if(!less(k,j)) break;               //不需要继续下沉
            
            exch(k,j);                          //交换父节点和较大子节点
  
            k = j;                              //向下更新k
        }
    }
  

• 图示

  image

• 实现在堆中返回最大值

    public Key delMax(){
        
        Key max = pq[1];            //保存最大值
  
        exch(1,N--);                //交换最后元素到1位置
    
        sink(1);                    //下沉进行堆有序化
  
        pq[N+1] = null;             //将最后置为null，实现删除
  
        return max;                 /将最大值进行返回
    }
  

二叉堆实现优先队列(priority queue)

• MaxPQ的构建

  • public class MaxPQ(Key extends Comparable<Key>>

    • MaxPQ()——创建一个优先队列

    • MaxPQ(int max)——创建固定大小的优先队列

    • MaxPQ(Key[] a)——从给定的数组中创建优先队列

    • void insert(Key k)——插入数据

    • Key max()——返回最大值

    • Key delMax()——删除最大值

    • boolean isEmpty()——判断队列是否为空

    • int size()——返回当前队列长度

• MaxPQ的实现

    /*
     *  此程序是一个优先队列(priority queue)数据结构的实现
     *  适用于我们无法保存大量的数据时候
     * 
     *  此时我们使用的是二叉堆——数组实现
     *  我们的下标是从1-N
     * 
     *  1. 插入数据——insert
     *  2. 返回最大值
     *  3. 判断队列是否空
     *  4. 当前队列长度
     * */
    
    public class MaxPQ<Key extends Comparable<Key>> {
        private Key[] pq;
        private int N = 0;
        
        //创建固定大小的优先队列
        public MaxPQ(int maxN){
            pq = (Key[]) new Comparable[maxN+1];
        }
        
        public boolean isEmpty() {
            return N == 0;
        }
        
        //插入数据
        public void insert(E e) {
            
            //插入到末尾
            pq[++N] = e;
            
            //swim
            swim(N);
        }   
    
        //删除最大值
        public Key delMax() throws Exception{
    
            if(isEmpty()) {
                throw new Exception("pq is empty");
            }
            
            //保存最大值
            Key max = pq[1];
            
            //交换最后一个和最大值
            exch(1,N--);
            
            //下沉交换上去的值
            sink(1);
            
            pq[++N] = null;
            
            return max;
        }
    
        //sink
        private void sink(int k) {
            // TODO Auto-generated method stub
            //将i下沉
            while(2 * k <= N) {
                int j = 2 * k;
                
                if(j < N && less(j, j+1)) j++;          //j指向较大的孩子的下标
                if(!less(k, j)) break;  
                
                exch(k,j);                              //交换父节点与较大的子孩子
                
                k = j;                                  //继续向下判断
            }
        }   
        
        //swim
        private void swim(int k) {
            // TODO Auto-generated method stub
            while(k > 1 && less(k/2,k)) {           //父小于子，则交换父子
                exch(k/2, k);
                k = k/2;
            }
        }
        
        private void exch(int i, int j) {
            // TODO Auto-generated method stub
            Key tmp = pq[i];
            pq[i] = pq[j];
            pq[j] = tmp;
        }   
    
        private boolean less(int i, int j) {
            // TODO Auto-generated method stub
            return pq[i].compareTo((E) pq[j]) < 0;
        }
    }

HeapSort的实现

• 实现方式

  堆排序的过程分为两步

    * Build Heap——创建一个堆，此时以大顶堆为例(Heap construction)
  
    * repeatedlly move the maximum key——(SortDown)
  

  注意的问题是

    * 堆的sink操作下标是1-N
  
    * 而传入的数组下标是0-N-1
  
    * 需要修改exch和less方法
  

• 第一步：Build heap using bottom-up method（利用自顶向下创建一个堆）

  • 因为叶子节点本身就是heap order，因此不需要进行排序，因此下标从N/2开始

  • 代码实现

      //build heap
      for(k = N/2; k >= 1;k--) {
          
          sink(a,k,N);                        
      }
    

• 第二步:repeatedlly move the maximum key

  • 思路

    • Remove the maximum,one at a time

    • leave in array, instead of nulling out

  • 代码实现

      //heap sort 
      
      while(N >= 1) {
          exch(a,1,N);            //交换第一个和最后一个            
          sink(a,1,--N);          //下沉
      }
    

• HeapSort的实现

    public class HeapSort {
        public static void sort(Comparable[] a) {
            int k;
            int N = a.length;
            
            //build heap
            for(k = N/2; k >= 1;k--) {
                sink(a,k,N);                    //此时的方向是从右向左                
            }
            
            //heap sort 
            while(N >= 1) {
                exch(a,1,N);                
                sink(a,1,--N);
            }
        }
    
    
        private static void sink(Comparable[] a, int k, int N) {
            // TODO Auto-generated method stub
            while(2 * k <= N) {                                     //将父节点与较大的子节点进行交换
                int j = 2 * k;
                
                if(j < N && less(a,j,j+1))   j++;                   //j指向较大子节点
                
                if(!less(a,k,j))  break;                            
                
                exch(a,k,j);                                        //交换父节点和最大子节点
                
                k = j;                                              //k继续向下进行判断
            }                                                       
        }   
    
        private static void exch(Comparable[] a, int i, int j) {
            
            i--;                    //因为堆是1——N，而数组是0——N-1
            j--;
            
            Comparable t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    
        private static boolean less(Comparable[] a,int i, int j) {
            // TODO Auto-generated method stub
            return a[--i].compareTo(a[--j]) < 0;
        }
    }
  

• 堆排序图示

image

小结

堆排序算法也是一种选择排序算法,每一次删除一个最大(delMax)或最小(delMin)

整体由堆的构建、堆的交换与下沉两个步骤组成。