• 欢迎光临~

堆与优先级队列

开发技术 开发技术 2022-12-22 次浏览

1. 二叉堆

1.1 二叉堆的定义

二叉堆在逻辑上是一颗完全二叉树,而在存储方式上还是用数组进行存储的。二叉堆具有如下性质,如果当前节点在数组中的索引为 ,那么有:

  • 其左子节点在数组中的索引为 (2i+1);
  • 其右子节点在数组中的索引为 (2i+2);
  • 其父节点在数组中的索引为 ((i-1)/2);

二叉堆的结构如下图所示:

堆与优先级队列

常见的二叉堆有两种形式,分别是【大根堆】和【小根堆】,其中前者的堆顶是整个序列中最大的元素,后者的堆顶则是整个序列中最小的元素。如果下标 i 满足 (0leq ileq (n-1)/2),其中 n 表示最后一个元素的下标,那么可以通过如下方法来判断当前序列为大根堆还是小根堆:

  • 大根堆:满足 arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]
  • 小根堆:满足 arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]

大根堆和小根堆如下图所示:

堆与优先级队列

1.2 二叉堆的操作

二叉堆的操作分为入堆出堆。入堆或者出堆后需要重新调整堆的结构,使其满足大根堆或者小根堆的条件,这个操作的过程分为【上浮】和【下沉】。

1.2.1 上浮

如图所示,为大根堆入堆后的上浮操作过程,先将入堆元素添加在数组末尾位置,然后与其父节点进行比较。对于大根堆而言,如果大于父节点,则与父节点交换位置;对于小根堆而言,如果小于父节点,则与父节点交换位置,重复上述操作,直到满足大根堆/小根堆的条件:

堆与优先级队列

1.2.2 下沉

如图所示,为大根堆出堆时的下沉操作过程,先将堆顶元素出堆,然后将数组最末尾位置的元素放入到堆顶位置,与其左、右子节点进行比较。对于大根堆而言,找出值最大的子节点并与其交换位置;对于小根堆而言,找出值最小的子节点并与其交换位置,重复上述操作,直到其满足大根堆/小根堆的条件:

堆与优先级队列

综上所述,无论是上浮操作还是下沉操作,其时间复杂度均为 (O(logn)),空间复杂度均为 (O(1))

1.3 优先级队列的实现

优先级队列的代码实现如下,可以通过传入不同的函数对象来创建大根堆/小根堆,当传入的函数对象为 greater<int>() 时为大根堆,为 less<int>() 时为小根堆:

class PriorityQueue {
public:
    using Comp = function<bool(int, int)>;

    PriorityQueue(int cap = 20, Comp comp = greater<int>());
    ~PriorityQueue();

    // 入堆
    void push(int val);
    // 出堆
    void pop();
    // 获取堆顶元素
    int top() const;
    // 堆大小
    int size() const;
    // 堆是否为空
    bool empty() const;
    // 打印堆
    void print() const;

private:
    // 上浮操作
    void siftUp(int idx, int val);
    // 下沉操作
    void siftDown(int idx, int val);
    // 数组扩容
    void expand(int size);

private:
    int* que_;  // 动态扩容的数组
    int  size_; // 数组元素的个数
    int  cap_;  // 数组的总空间大小
    Comp comp_; // 比较器对象
};

PriorityQueue::PriorityQueue(int cap, Comp comp)
    : que_(new int[cap])
    , size_(0)
    , cap_(cap)
    , comp_(comp) {
}

PriorityQueue::~PriorityQueue() {
    delete[] que_;
    que_ = nullptr;
}

void PriorityQueue::push(int val) {
    if (size_ == cap_) expand(cap_ * 2);

    if (size_ == 0) {
        que_[size_] = val;
    } else {
        siftUp(size_, val);
    }
    size_++;
}

void PriorityQueue::pop() {
    if (size_ == 0)
        throw "priority queue is empty";
    size_--;
    if (size_ != 0) {
        siftDown(0, que_[size_]);
    }
}

int PriorityQueue::top() const {
    if (size_ == 0)
        throw "priority queue is empty";
    return que_[0];
}

int PriorityQueue::size() const {
    return size_;
}

bool PriorityQueue::empty() const {
    return size_ == 0;
}

void PriorityQueue::print() const {
    for (int i = 0; i < size_; i++) {
        cout << que_[i] << " ";
    }
    cout << endl;
}

void PriorityQueue::siftUp(int idx, int val) {
    while (idx > 0) {
        int father = (idx - 1) / 2;
        if (comp_(val, que_[father])) {
            que_[idx] = que_[father];
            idx       = father;
        } else {
            break;
        }
    }

    que_[idx] = val;
}

void PriorityQueue::siftDown(int idx, int val) {
    // 下沉时不能超过最后一个有孩子的节点
    while (idx < size_ / 2) {
        int child = 2 * idx + 1;
        if (child + 1 < size_ && comp_(que_[child + 1], que_[child])) {
            // 有右孩子 且右孩子的值大于左孩子 则将其更新为右孩子
            child++;
        }

        if (comp_(que_[child], val)) {
            que_[idx] = que_[child];
            idx       = child;
        } else {
            break;
        }
    }

    que_[idx] = val;
}

void PriorityQueue::expand(int size) {
    int* p = new int[size];
    memcpy(p, que_, cap_ * sizeof(int));
    delete[] que_;
    que_ = p;
    cap_ = size;
}

2. STL实现

2.1 heap

heap 并不属于 STL 的容器组件,它是 priority queue 的底层容器,实现了二叉堆数据结构。priority queue 允许用户以任何次序将任何元素推入容器内,但取出时一定是从优先级最高的元素开始取,因此称作【优先级队列】。

heap 的实现是通过一个完全二叉树,即整棵二叉树除了最底层的叶节点之外,是填满的,而最底层的叶节点由左至右又不得有空隙。

SGI STL 中将此数组以 vector 来代替。根据元素排列方式,heap 可以分为【max-heap(大根堆)】和【min-heap(小根堆)】两种,前者每个节点的键值都大于或等于其子节点键值,后者的每个节点键值都小于或等于其子节点键值。因此,前者的最大值在根节点,并位于数组的起始处,而后者的最小值在根节点,并位于数组的起始处。STL 提供的是 max-heap

heap 所有元素都必须遵循特别的完全二叉树排列规则,所以 heap 不提供遍历功能,也不提供迭代器。

2.2 priority queue

priority queue 是一个拥有权值观念的 queue,它允许加入新元素,移除旧元素,审视元素值等功能。由于这是一个 queue,所以只允许在底端加入元素,并从顶端取出元素,除此之外别无其他存取元素的途径。

priority queue 带有权值观念,其内的元素并非按照被推入的次序排列,而是自动依照元素的权值排列。权值最高者,排在最前面。

缺省情况下,priority queue 利用一个 max-heap 完成。

堆与优先级队列

注意:pop() 并不是真的将元素弹出,而是重排 heap,然后再以底层容器的 pop_back() 取得被弹出的元素。priority queue 不提供遍历功能,也不提供迭代器。

程序员灯塔
转载请注明原文链接:堆与优先级队列
喜欢 (0)