算法编程Web前端之路让前端飞

排序算法08:优先队列与堆排序

2017-05-04  本文已影响40人  梦中人在梦中

堆排序一种是基于二叉堆的排序。本文将从优先队列讲起,循序渐进的实现堆排序。这也是《算法》第四版上讲解堆排序的大致章节结构。另外,本文所有的图都来自于此书。

优先队列

普通队列是一种先进先出的数据结构,先放进队列的元素取值时优先被取出来。而优先队列是一种具有最高优先级元素先出的数据结构,比如每次取值都取最大的元素。

优先队列有两个核心方法,一个是insert(val)向队列中添加元素,另外一个是delMax()删除最大元素(优先级最高的)并返回。可以考虑使用数组来存储优先队列的数据。

优先队列有如下三种实现方式:

  1. 有序数组(调用insert方法时使用类似插入排序把新增元素放到正确位置,调用delMax方法时直接取数组最后一个元素,因为此时元素已经是有序状态)
  2. 无序数组(调用insert方法时直接把元素放到数组中,调用dexMax方法时使用类似选择排序的方法从数组中找出最大元素,删除并返回)
优先队列时间复杂度对比与演示

堆的算法

优先队列可以使用一棵堆有序的二叉树来解决。什么叫做堆有序呢?当一棵二叉树的每个几点都大于它的两个子节点时,它被称为堆有序。那么,根节点就是堆有序的二叉树中的最大节点。

二叉堆可以使用数组来存储。为了方便起见,根节点放在位置1处(位置0不使用),它的两个子节点分别放在位置2和位置3。同理可知,在一个堆中,位置k的节点的父节点的位置为k/2,而它的两个子节点的位置则分别为2k和2k+1.我们就可以这样在树的上下移动:访问a[k]节点的上一层就令k等于k/2,向下一层就令k等于2k或2k+1.

如下图所示:

堆的表示

使用二叉堆,我们就能实现对数级别的插入元素和删除最大元素。

由下自上的堆有序化(上浮)

当调用优先队列的insert方法时,我们首先把元素放置到数组的结尾,然后再把该元素上浮到正确的节点,最终形成堆有序状态。

代码如下:

    //下标为k的元素上浮到正确位置
    function swim(arr,k) {
        while(k>1 && less(arr,parseInt(k/2),k)){
            //父节点索引
            var parentNode = parseInt(k/2);
            exch(arr,parentNode,k);
            k = parentNode;
        }
    }

由上至下的堆有序化(下沉)

当调用优先队列的delMax方法时,我们下标为1的元素(最大元素)和数组最后一个元素交换,返回最大元素,数组长度减去1,即删除最后一个元素。此时的位置1元素不一定是最大元素,就需要下沉到正确位置,重新构造有序堆。

代码如下:

    //下标为k的元素下沉到正确位置
    function sink(arr,k,len) {
        var len = len ||arr.length;
        while(2*k <= len){
            var j = 2*k;
            if(j<len && less(arr,j,j+1)) j++;
            if(!less(arr,k,j)) break;
            exch(arr,k,j);
            k = j;
        }
    }

堆有序化示例图:

堆有序化

堆的操作示例图:

堆的操作

优先队列实现

理解了实现堆有序的上浮和下沉两种方法,优先队列的实现就轻而易举了,代码如下:

    /**
     * 优先队列
     * @constructor
     */
    function MaxQueue() {
        this.queue = [];                //- 存储基于堆的完全二叉树
        this.len   = 0;                 //- 存储于queue[1..len]中,queue[0]未使用
    }

    /**
     * 向优先队列中插入元素
     * @param val
     */
    MaxQueue.prototype.insert = function (val) {
        this.queue[++this.len] = val;    //- 从索引1开始添加元素
        //使新增元素上浮到树的正确位置
        swim(this.queue,this.len);
    };

    /**
     * 删除优先队列中的最大元素,并返回该元素
     * @returns {*}
     */
    MaxQueue.prototype.delMax = function () {
        var max = this.queue[1];        //- 从根节点得到最大元素
        exch(this.queue,1,this.len--);  //- 把最后一个节点放到根节点上,并且让长度索引减一
        this.queue.length = this.len+1; //- 删除最后一个节点
        sink(this.queue,1);             //- 下沉根节点,恢复堆的有序性
        return max;
    };

    MaxQueue.prototype.show = function () {
        console.log(this.queue);
    };

    MaxQueue.prototype.isEmpty = function () {
        return this.len==0;
    };

示例图:

堆上的优先队列操作

堆排序

理解了优先队列,堆排序的逻辑十分简单。第一步:让数组形成堆有序状态;第二步:把堆顶的元素放到数组最末尾,末尾的放到堆顶,在剩下的元素中下沉到正确位置,重复操作即可。

代码如下:

    /**
     * 堆排序算法
     * @constructor
     */
    function HeapSort() {}
    HeapSort.prototype.sort = function (arr) {
        var len = arr.length;
        //由于arr[0]不使用,放到最后使得能够被排序
        //注意:也可在less和exch中解决,见后面的Java完整代码实现。这里为了对应位置1的元素不使用,方便对照看代码与样例图。
        arr[len] = arr[0];
        //使用下沉来构造二叉堆
        for(var k=parseInt(len/2);k>=1;k--){
            sink(arr,k,len);
        }
        //不断把最大的arr[1]交换到最后,然后让新的arr[1]元素下沉到堆有序状态
        while (len>1){
            exch(arr,1,len--);
            sink(arr,1,len);
        }
        //删除未使用的arr[0](也可在less和exch中解决,见Java代码实现)
        arr.splice(0,1);
    };

示例图:

堆排序

完整代码

Javascript实现

/**
 * Created by YiYing on 2017/5/2.
 */
(function (W) {

    /**
     * 优先队列
     * @constructor
     */
    function MaxQueue() {
        this.queue = [];                //- 存储基于堆的完全二叉树
        this.len   = 0;                 //- 存储于queue[1..len]中,queue[0]未使用
    }

    /**
     * 向优先队列中插入元素
     * @param val
     */
    MaxQueue.prototype.insert = function (val) {
        this.queue[++this.len] = val;    //- 从索引1开始添加元素
        //使新增元素上浮到树的正确位置
        swim(this.queue,this.len);
    };

    /**
     * 删除优先队列中的最大元素,并返回该元素
     * @returns {*}
     */
    MaxQueue.prototype.delMax = function () {
        var max = this.queue[1];        //- 从根节点得到最大元素
        exch(this.queue,1,this.len--);  //- 把最后一个节点放到根节点上,并且让长度索引减一
        this.queue.length = this.len+1; //- 删除最后一个节点
        sink(this.queue,1);             //- 下沉根节点,恢复堆的有序性
        return max;
    };

    MaxQueue.prototype.show = function () {
        console.log(this.queue);
    };

    MaxQueue.prototype.isEmpty = function () {
        return this.len==0;
    };

    W.MaxQueue = MaxQueue;


    /**
     * 堆排序算法
     * @constructor
     */
    function HeapSort() {}
    HeapSort.prototype.sort = function (arr) {
        var len = arr.length;
        //由于arr[0]不使用,放到最后使得能够被排序
        //注意:也可在less和exch中解决,见后面的Java完整代码实现。这里为了对应位置1的元素不使用,方便对照看代码与样例图。
        arr[len] = arr[0];
        //使用下沉来构造二叉堆
        for(var k=parseInt(len/2);k>=1;k--){
            sink(arr,k,len);
        }
        //不断把最大的arr[1]交换到最后,然后让新的arr[1]元素下沉到堆有序状态
        while (len>1){
            exch(arr,1,len--);
            sink(arr,1,len);
        }
        //删除未使用的arr[0](也可在less和exch中解决,见Java代码实现)
        arr.splice(0,1);
    };

    W.HeapSort = HeapSort;


    //下标为k的元素上浮到正确位置
    function swim(arr,k) {
        while(k>1 && less(arr,parseInt(k/2),k)){
            //父节点索引
            var parentNode = parseInt(k/2);
            exch(arr,parentNode,k);
            k = parentNode;
        }
    }

    //下标为k的元素下沉到正确位置
    function sink(arr,k,len) {
        var len = len ||arr.length;
        while(2*k <= len){
            var j = 2*k;
            if(j<len && less(arr,j,j+1)) j++;
            if(!less(arr,k,j)) break;
            exch(arr,k,j);
            k = j;
        }
    }

    function less(arr,m,n) {
        //可根据不同的数据类型设置比对规则,比如json。这里适用于数字与字符串。
        return arr[m]<arr[n];
    }

    /**
     * 交换数组arr中m与n的位置
     * @param m
     * @param n
     */
    function exch(arr,m,n) {
        var swap    = arr[m];
        arr[m]      = arr[n];
        arr[n]      = swap;
    }


})(window);

//测试代码
(function () {
    //优先队列测试,依次从大到小输出元素
    var q = new MaxQueue();
    q.insert(3);
    q.insert(33);
    q.insert(9);
    q.insert(21);
    while (!q.isEmpty()){
        console.log(q.delMax())
    }

    //堆排序测试代码
    var arr = [4,5,6,0,3,5,21,7,9,0,1];
    new HeapSort().sort(arr);
    console.log(arr);
})();

Java实现

package com.algs;

public class Heap {
    /**
     * 堆排序
     * @param pq
     */
    public static void sort(Comparable[] pq) {
        int n = pq.length;
        //构造堆结构
        for (int k = n/2; k >= 1; k--)
            sink(pq, k, n);
        //排序数组
        while (n > 1) {
            exch(pq, 1, n--);
            sink(pq, 1, n);
        }
    }

    //下沉元素
    private static void sink(Comparable[] pq, int k, int n) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && less(pq, j, j+1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }

    //注意这里i和j都减去1
    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;
    }
    //注意这里i和j都减去1
    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i-1];
        pq[i-1] = pq[j-1];
        pq[j-1] = swap;
    }

    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    public static void main(String[] args) {
        String[] a = {"S","O","R","T","E","X","A","M","P","L","E"};
        Heap.sort(a);
        show(a);
    }
}

总结

  1. 不稳定。
  2. 原地排序。
  3. 时间复杂度为NlogN
  4. 空间复杂度为l

GitHub:https://github.com/AlbertKnag/algs-practice

上一篇:<a href="http://muchstudy.com/2017/04/30/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%9507%EF%BC%9A%E4%B8%89%E5%90%91%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F/">排序算法07:三向快速排序</a>
下一篇:<a href="http://muchstudy.com/2017/05/04/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%9509%EF%BC%9A%E6%80%BB%E7%BB%93/">排序算法09:总结</a>

上一篇下一篇

猜你喜欢

热点阅读