算法笔记(JavaScript版)——优先队列

堆的算法

优先队列是一种抽象数据类型,最重要的操作是删除最大元素和插入元素。

用长度为N+1的数组pq[]来表示一个大小为N的堆,堆元素放在pq[1]至pq[N]中,不使用pq[0]。

function MaxPQ(){
  var pq = [],
      n = 0;

  this.show = function(){
    console.log(pq);
  }
  this.insert = function(v){
    pq[++n] = v;
    swim(n);
  }
  this.delMax = function(){
    var max = pq[1];
    exch(1, n--);
    pq[n+1] = null;
    sink(1);
    return max;
  }
  //由下至上的堆有序化(上浮)的实现
  function swim(k){
    while((k > 1) && less(Math.floor(k/2), k)){
      exch(Math.floor(k/2), k);
      k = Math.floor(k/2);
    }
  }

  //由上至下的堆有序化(下沉)的实现
  function sink(k){
    while(2*k <= n){
      var j = 2*k;
      if((j < n) && less(j, j+1)){
        j++;
      }
      if(!less(k, j)){
        break;
      }
      exch(k, j);
      k = j;
    }
  }

  //堆实现的比较和交换方法
  function less(i, j){
    return pq[i] < pq[j];
  }
  function exch(i, j){
    var temp = pq[i];
    pq[i] = pq[j];
    pq[j] = temp;
  }
}

关键字:JavaScript, 算法, function, exch

本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击下方“内容举报”进行投诉反馈!

相关文章

立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部