学习与记录。

0%

优先队列的基础实现

发表于 更新于 分类于 Valine：

本文主要记录优先队列的基础实现（C#）。

代码

要求泛型实现 IComparable<T> 接口，这样才可以对容器内的对象进行比较。

1
2
3
4
public class PriorityQueue<T> where T : IComparable<T> 
{
	
}

字段

底层容器为数组，比较器可以使用 IComparer<T> 接口实现，也可以使用 Comparison 委托实现。

从规范的角度来讲，使用 IComparer<T> 接口可能会更好（将比较器留给泛型类自行实现），这样在构造优先队列的时候既不需要传入比较器，也可以对泛型类进行一定的限制。

如果对比较器有要求也可以在构造时自定义比较器，后面的实际应用会提到如何传入自定义的比较器。

1
2
3
4
private const int _DEFAULT_CAPACITY = 0x10; // 默认的初始容量

private readonly IComparer<T> _comparer; // 比较器
private T[] _heap; // 二叉堆

属性

1
2
3
4
5
public int Capacity => _heap.Length; // 容量

public int Count { get; private set; } // 实际的元素数量

public bool IsEmpty => Count == 0; // 是否为空

方法

构造方法

1
2
3
4
5
6
7
8
public PriorityQueue(IComparer<T> comparer)
    : this(_DEFAULT_CAPACITY, comparer) { }

public PriorityQueue(int capacity = _DEFAULT_CAPACITY, IComparer<T> comparer = null)
{
    _heap = new T[capacity];
    _comparer = comparer ?? Comparer<T>.Default; // 形参为空则获得默认比较器
}

扩容 Expand

使用 Array 类的静态方法 Resize 进行扩容，将当前队列的容量扩容为之前的两倍。

1
2
3
4
private void Expand()
{
    Array.Resize(ref _heap, Capacity * 2);
}

缩容 Shrink

使用 Array 类的静态方法 Resize 进行缩容，将当前队列的容量缩容为之前的一半。

1
2
3
4
private void Shrink()
{
    Array.Resize(ref _heap, Capacity / 2);
}

获取头元素 Peek

判断队列是否为空，是则抛出异常，否则返回堆的头元素。

1
2
3
4
5
6
7
8
public T Peek()
{
    if (IsEmpty) {
        throw new InvalidOperationException("优先队列为空，获取头元素失败。");
    }

    return _heap[0];
}

入队 Enqueue

判断队列容量是否已满，是则进行扩容；

然后将新元素放在队列的末尾，同时队列实际长度 +1；

最后对队列进行自底向上的调整。

1
2
3
4
5
6
7
8
9
public void Enqueue(T item)
{
    if (Count == Capacity) {
        Expand();
    }

    _heap[Count++] = item;
    HeapAdjustFromBottom();
}

自底向上调整堆 HeapAdjustFromBottom

将新入堆的元素上升到其该在的位置，详细见注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void HeapAdjustFromBottom()
{
    // child 为子元素的下标，即新入队元素的下标
    int child = Count - 1;
    T value = _heap[child];
    // parent 为父元素的下标
    for (int parent = (child - 1) / 2; parent >= 0 && child > 0; parent = (parent - 1) / 2) {
        // 判断子元素和父元素的关系，不满足则跳出
        if (_comparer.Compare(value, _heap[parent]) <= 0) {
            break;
        }
        // 满足则将父元素下沉，然后更新子元素的下标
        _heap[child] = _heap[parent];
        child = parent;
    }
    // 将子元素放在最终确定的位置
    _heap[child] = value;
}

出队 Dequeue

判断队列是否为空，是则抛出异常；

然后将头元素出队，队列实际长度 -1，并用队列的尾元素补上头元素；

若出队后，实际的元素数量小于等于容量的一半，则进行一次缩容；

最后对队列进行自顶向下的调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public T Dequeue()
{
    if (IsEmpty) {
        throw new InvalidOperationException("优先队列为空，出队失败。");
    }

    T item = _heap[0];
    _heap[0] = _heap[--Count];
    HeapAdjustFromTop();
    if (Count * 2 <= Capacity) {
        Shrink();
    }
    return item;
}

自顶向下调整堆 HeapAdjustFromTop

将新的头元素下沉到其该在的位置，详细见注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void HeapAdjustFromTop()
{
    // parent 为父元素的下标，即新头元素的下标
    int parent = 0;
    T value = _heap[0];
    // child 为子元素的下标
    for (int child = parent * 2 + 1; child < Count; child = child * 2 + 1) {
        // 找到目标子元素
        if (child < Count - 1 && _comparer.Compare(_heap[child], _heap[child + 1]) < 0) {
            ++child;
        }
        // 判断子元素和父元素的关系，不满足则跳出
        if (_comparer.Compare(_heap[child], value) <= 0) {
            break;
        }
        // 满足则将子元素上升，同时更新父元素的下标
        _heap[parent] = _heap[child];
        parent = child;
    }
    // 将父元素放在最终确定的位置
    _heap[parent] = value;
}

完整代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public class PriorityQueue<T> where T : IComparable<T>
{
    private const int _DEFAULT_CAPACITY = 0x10; // 默认的初始容量

    private readonly IComparer<T> _comparer; // 比较器
    private T[] _heap; // 二叉堆

    public PriorityQueue(int capacity = _DEFAULT_CAPACITY, IComparer<T> comparer = null)
    {
        _heap = new T[capacity];
        _comparer = comparer ?? Comparer<T>.Default;
    }

    public int Capacity => _heap.Length;

    public int Count { get; private set; }

    public bool IsEmpty => Count == 0;

    private void Expand()
    {
        Array.Resize(ref _heap, Capacity * 2);
    }

    private void Shrink()
    {
        Array.Resize(ref _heap, Capacity / 2);
    }

    public void Enqueue(T item)
    {
        if (Count == Capacity) {
            Expand();
        }

        _heap[Count++] = item;
        HeapAdjustFromBottom();
    }

    public T Dequeue()
    {
        if (IsEmpty) {
            throw new InvalidOperationException("优先队列为空，出队失败。");
        }

        T item = _heap[0];
        _heap[0] = _heap[--Count];
        HeapAdjustFromTop();
        if (Count * 2 <= Capacity) {
            Shrink();
        }
        return item;
    }

    private void HeapAdjustFromTop()
    {
        // parent 为父元素的下标，即新头元素的下标
        int parent = 0;
        T value = _heap[0];
        // child 为子元素的下标
        for (int child = parent * 2 + 1; child <= Count - 1; child = child * 2 + 1) {
            // 找到目标子元素
            if (child < Count - 1 && _comparer.Compare(_heap[child], _heap[child + 1]) < 0) {
                ++child;
            }
            // 判断子元素和父元素的关系，不满足则跳出
            if (_comparer.Compare(_heap[child], value) <= 0) {
                break;
            }
            // 满足则将子元素上升，同时更新父元素的下标
            _heap[parent] = _heap[child];
            parent = child;
        }
        // 将父元素放在最终确定的位置
        _heap[parent] = value;
    }

    private void HeapAdjustFromBottom()
    {
        // child 为子元素的下标，即新入队元素的下标
        int child = Count - 1;
        T value = _heap[child];
        // parent 为父元素的下标
        for (int parent = (child - 1) / 2; parent >= 0 && child > 0; parent = (parent - 1) / 2) {
            // 判断子元素和父元素的关系，不满足则跳出
            if (_comparer.Compare(value, _heap[parent]) <= 0) {
                break;
            }
            // 满足则将父元素下沉，然后更新子元素的下标
            _heap[child] = _heap[parent];
            child = parent;
        }
        // 将子元素放在最终确定的位置
        _heap[child] = value;
    }

    public T Peek()
    {
        if (IsEmpty) {
            throw new InvalidOperationException("优先队列为空，获取头元素失败。");
        }

        return _heap[0];
    }
}

实际应用

自定义比较器

下面以 int 作为例子，分别向优先队列中传入升序（其实 int 本身的比较器就是升序）和降序的比较器。

分别创建 int 对应的升序和降序类，实现 IComparer<T> 接口，T 为 int。

在接口方法中实现对应的升序和降序比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Test
{
    // int 升序类
    private class Asc : IComparer<int>
    {
        public int Compare(int x, int y) { return y - x; }
    }

    // int 降序类
    private class Desc : IComparer<int>
    {
        public int Compare(int x, int y) { return x - y; }
    }
    
    private readonly PriorityQueue<int> _btmHeap; // 本质小根堆
    
    private readonly PriorityQueue<int> _topHeap; // 本质大根堆
    
    public Test()
    {
        _btmHeap = new PriorityQueue<int>(new Asc()); // 小根堆对应升序比较器
        _topHeap = new PriorityQueue<int>(new Desc()); // 大根堆对应降序比较器
    }
}

LeetCode

LeetCode-295-困难-数据流的中位数

该题使用了两个优先队列，分别对应大根堆和小根堆。

代码

这里只放上 MedianFinder 类的内容，省略了优先队列类，提交时需要加上。

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
public class MedianFinder
{
    private readonly PriorityQueue<int> _topHeap; // 大顶堆，存储左半边数据
    private readonly PriorityQueue<int> _btmHeap; // 小顶堆，存储右半边数据

    public MedianFinder()
    {
        _topHeap = new PriorityQueue<int>(new Desc());
        _btmHeap = new PriorityQueue<int>(new Asc());
    }

    private int Count => _topHeap.Count + _btmHeap.Count;

    public void AddNum(int num)
    {
        if (Count % 2 == 0) {
            _topHeap.Enqueue(num);
            _btmHeap.Enqueue(_topHeap.Dequeue());
        } else {
            _btmHeap.Enqueue(num);
            _topHeap.Enqueue(_btmHeap.Dequeue());
        }
    }

    public double FindMedian()
    {
        if (Count % 2 == 0) {
            return (_topHeap.Peek() + _btmHeap.Peek()) / 2.0;
        }
        
        return _btmHeap.Peek();
    }

    private class Asc : IComparer<int>
    {
        public int Compare(int x, int y)
        {
            return y - x;
        }
    }

    private class Desc : IComparer<int>
    {
        public int Compare(int x, int y)
        {
            return x - y;
        }
    }
}

执行结果

result