优先队列与堆排序

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

优先队列

　　二叉堆可分为大根堆和小根堆，在大根堆中，每个节点将大于或等于它的两个子节点，因此，根节点为大根堆的最大节点。可以使用数组表示二叉堆，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;
}

　　完整的代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
template <typename T>
class PriorityQueue
{
public:
    PriorityQueue()
        : n( 0 ), x( 1 )
    { 
    }
    void push( const T &elem )
    {
        ++n;
        x.push_back( elem );
        
        for( int i = n; i > 1 && x[i] > x[i / 2]; i /= 2 )
        {
            swap( x[i], x[i / 2] );
        }
    }
    
    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;
    }
    
    bool empty() const
    {
        return n == 0;
    }
    int size() const
    {
        return n;
    }
private:
    int        n;
    vector<T>  x;
};

堆排序

　　当我们了解了优先队列的实现原理，堆排序就容易实现了：

  • 先是构造大根堆。
  • 将数组分成两部分，x[1, ..., i]表示堆, x[i + 1, ..., n]表示排定的数组。
  • 交换x[1]和x[i]，这时，x[2, ..., i - 1]表示堆，x[i, ..., n]表示排定的数组。
  • 将x[1]下移到合适位置，这时，x[1, ..., i - 1]表示堆，x[i, ..., n]表示排定的数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
    make max-heap, the max element in x[1]
 **/
template <typename T>
void siftUp( T x[], int n )
{
    for( int i = n; i > 1 && x[i] > x[i / 2]; i /= 2 )
    {
        swap( x[i], x[i / 2] );
    }
}
/**
    move x[1] down to the proper position
**/
template <typename T>
void siftDown( T x[], int n )
{
    int p;
    for( int i = 1; ( p = 2 * i ) <= n; i = p )
    {
        if( p < n && x[p] < x[p + 1] )
        {
            ++p;
        }
        if( x[i] >= x[p] )
        {
            break;
        }
        swap( x[i], x[p] );
    }
}
template <typename T>
void heap_sort( T arr[], int n )
{
    T *x = arr - 1;           // must minus 1
    
    for( int i = 2; i <= n; ++i )
    {
        /**
            invariant: x[1, ..., i - 1] is a heap
        **/
        siftUp( x, i );
        /**
            now x[1, ..., i] is a heap
        **/
    }
    for( int i = n; i >= 2; --i )
    {
        /**
            x[1, ..., i] is a heap, x[i + 1, ..., n] is sorted
        **/
        swap( x[i], x[1] );
        /**
            x[2, ..., i - 1] is heap, x[i, ..., n] is sorted
        **/
        siftDown( x, i - 1 );
        /**
            x[1, ..., i - 1] is heap, x[i, ..., n] is sorted
        **/
    }
}

参考资料