乐趣区

关于算法-数据结构:优先队列

优先队列有什么用?

能够求一些数据里的最大几个值,能够设定事件程序。

为什么不间接排序后再从头拿?

假如数据量很大时,比方 1 亿个选 10 个最大的,你排好序内存可能装不下。优先队列只有 10 个空间,间接往队列尾巴插入就行。

根底

优先队列的根底是把数据结构齐全二叉树构造,用数组实现。

树的个性
  1. 父节点比任何一个子节点大。
  2. 父节点的地位是 k,子节点别离是 2k 和 2k+1

优先队列应用时,每次都从根节点拿数据,而后从新调整树结构。

插入与删除

插入时,数据插入到尾部,而后用【上浮】操作使其到适合地位,达成有序。

public void insert(Key v){pq[++N] = v;
        swim(N);
}

删除时,移除删除节点,同时把尾部的节点换到删除地位,而后用【下沉】操作使其到适合地位,达成有序。

/**
 * 删除。该数组 0 地位不存数据,从 1 开始存。* @return
*/
public Key deleteMax(){Key key = pq[1];
    exchange(1, N--);
    pq[N+1] = null;
    sink(1);
    return key;
}
上浮

对应插入操作。新插入的数据放在开端,它必然突破了本来树的有序性。这时须要将插入的节点和父节点比拟。

如果该节点比父节点大,则替换他们地位。达成【父节点比子节点大】这个个性。而后再一直与上一级的父节点比拟,直到满足个性。

// 由个性 2 得:当子节点是 k 时,父节点地位是 k /2
private void swim(int k){while (k > 1 && less(k/2, k)){exchange(k, k/2);
            k = k/2;
        }
}
下沉

对应删除操作。原先删除的地位被最尾部的节点取代,这也突破了树的有序性。这时该节点要和和子节点比拟,首先得有子节点,其次要选大的那个子节点(这样选出来的节点能力胜任父节点),说白了就是该节点,与两个子节点之间选个最大的当父节点。选到适合的子节点作为父节点后,再往一直下一级比拟,直到没有子节点或者有序。

private void sink(int k){
        // 这个条件是保障有叶子节点
        while (2 * k < N){
            // 左子节点的坐标
            int j = 2 * k;
            // 这一段是比拟左右叶子节点哪个大,要选大的那个
            if(j < N && less(j, j+1)){j++;}
            // 如果 k > j, 阐明排序失常,间接退出,k < j 时替换它们的地位,持续向下比拟
            if(!less(k, j)){break;}
            exchange(k, j);
            k = j;
        }
    }
Java 里有对应的实现

线程平安:PriorityBlockingQueue

线程不平安:PriorityQueue

退出移动版