M010K
0%

对优先队列的改进

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 681 阅读时长 ≈ 1 分钟
通过减少交换次数，对优先队列的sink和swim方法进行优化

优先队列改进

1.对sink和swim方法的改善

主要是将元素的交换改为直接赋值，减少操作步数，在数据量较大的时候对性能有一定的提高

  • 原始操作，交换两元素
1
2
3
4
5
6
7
8
private void swim(int k)
{
    while (k > 1 && greater(k/2, k))
    {
        exch(k, k/2);
        k = k / 2;
    }
}
  • 优化后
1
2
3
4
5
6
7
8
9
10
private void swim(int k)
{
    pq[0] = pq[k];
    while (k > 1 && greater(k/2, 0))
    {
        pq[k] = pq[k/2];
        k = k / 2;
    }
    pq[k] = pq[0];
}
  • 原始操作，交换两元素
1
2
3
4
5
6
7
8
9
10
11
private void sink(int k)
{
    while (2*k <= n)
    {
        int j = 2*k;
        if (j < n && greater(j, j+1)) j++;
        if (!greater(k, j)) break;
        exch(k, j);
        k = j;
    }
}
  • 优化后
1
2
3
4
5
6
7
8
9
10
11
12
13
private void sink(int k)
{
    pq[0] = pq[k];
    while (2*k <= n)
    {
        int j = 2*k;
        if (j < n && greater(j, j+1)) j++;
        if (!greater(0, j)) break;
        pq[k] = pq[j];
        k = j;
    }
    pq[k] = pq[0];
}