发表于   |   分类于   |   阅读次数

优先队列

　　二叉堆可分为大根堆和小根堆，在大根堆中，每个节点将大于或等于它的两个子节点，因此，根节点为大根堆的最大节点。可以使用数组表示二叉堆，x[0]弃之不用，我们用x[1]表示根节点。假定堆有 n 个元素并且满足大根堆的属性，那么需要满足 x[i] <= x[i/2] ( n 取值 [2, n] )。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T>
class PriorityQueue
{
public:
    PriorityQueue()
        : n( 0 ), x( 1 )
    {
    }
    void push( const T &elem ) 
    { 
    }
    T pop()
    {
    }
private:
    int        n;          // for nodes' number
    vector<T>  x;
};

　　往堆中加入新节点：

1
2
3
4
5
void push( const T &elem )
{
    ++n;
    x.push_back( elem );
}

　　新节点位于x[n]，这时x[1, ..., n]可能不满足堆的属性：

  • 要是新节点大于它的父节点，则交换它们。
  • 持续这个过程，直到新节点不大于它的父节点，即小于或等于它的父节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void push( const T &elem )
{
    ++n;
    x.push_back( elem );
    /**
        invariant: 
        x[1, ..., n] is heap except perhaps x[i] and x[i / 2]
    **/
    for( int i = n; i > 1 && x[i] > x[i / 2]; i /= 2 )
    {
        swap( x[i], x[i / 2] );
    }
}

　　另一个操作时pop()，也就是将最大的节点移除优先队列：

1
2
3
4
5
6
7
8
T pop()
{
    T maxElem = x[1];
    /**
        remove x[1], now x[2, ..., n] is a heap, our goal is make x[1, ..., n - 1] be a heap
    **/
    return maxElem;
}

　　移出了最大的节点x[1]，为了维持堆的属性，可以这样做：

  • 将最后一个节点elem放到x[1]，n减一 。
  • 为了维持堆的属性，要是elem小于它的两个子节点的较大者，交换他们。
  • 持续这个过程，直到elem大于或等于它的两个子节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
T pop()
{
    T maxElem = x[1];
    x[1] = x[n--];
    x.pop_back();
		
    int p;
    for( int i = 1; ( p = i * 2 ) <= n; i = p )
    {
        if( p < n && x[p] < x[p + 1] )
        {
            ++p;
        }
        if( x[i] >= x[p] )
        {
            break;
        }
        swap( x[i], x[p] );
    }
    return maxElem;
}
阅读全文 »