数据结构与算法：堆与优先队列

2023-09-23

字数统计: 914字 | 阅读时长≈ 3分

堆

堆的概念和性质

堆（Heap）：堆是一棵完全二叉树，且满足以下性质：

堆的堆顶元素是最大（或最小）的。
堆中每个节点的值都大于（或小于）其左右孩子节点的值。

堆的实现

以小顶堆为例，因为堆是一棵完全二叉树，所以可以使用数组来模拟堆。

假设我们现在有一数组，可以将该数组调整为堆，调整时，需要从最后一个非叶子节点开始调整，因为叶子节点没有孩子节点，所以调整时，只需要调整非叶子节点即可，它的整体调整过程是自下而上然后自上而下的。

调整过程：比较节点与它的左右孩子。将最小的节点放在父节点。

假设有一数组需要调整为堆，数组下标从0开始，从n/2-2位置开始调整，一直到0的位置。
假如要调整为大顶堆，代码如下：
本段代码将数组调整为一个大顶堆，若要调整为小顶堆，只需要改变比较条件即可（将大于号改为小于号）——将最大值置于父节点。

void Heapify(int* arr,int n,int i)
{
   int largest = i;
   int left = 2 * i + 1;
   int right = 2 * i + 2;

   while (true) {
       if (left < n && arr[left] > arr[largest]) {
           largest = left;
       }

       if (right < n && arr[right] > arr[largest]) {
           largest = right;
       }

       if (largest == i) {
           break;
       }

       swap(arr[i], arr[largest]);
       i = largest;
       left = 2 * i + 1;
       right = 2 * i + 2;
   }
}

//对堆进行测试，arr为数组，n为数组长度
void TestHeapif(int* arr,int n)
{
    for(int i=n/2-1;i>=0;i--){
        Heapify(arr,n,i);
    }
}

堆的一些操作

堆的插入操作，依旧以数组作为堆的实现：
插入时，只需将新元素插入到数组对下标对应的位置，然后对新元素的父节点进行调整即可。

//n为插入的位置，val为插入的元素
void HeapInsert(int* arr,int n,int val)
{
    arr[n]=val;
    Heapify(arr,n/2,1);
}

堆的删除操作，同样以数组作为堆的实现：
删除时，只需将要将堆顶元素与最后一个元素交换，然后删除最后一个元素，然后对新堆顶元素进行调整即可。

//n为数组长度
void HeapDelete(int* arr,int n)
{
    swap(arr[0],arr[n]);
    Heapify(arr,n-1,0);
}

优先队列

优先队列的概念

优先队列是一种基于堆的数据结构，它就有以下性质：

优先队列中的元素会按照优先级排列。
优先级最高的元素总是最先出队。

优先队列的实现

优先队列可以看作是堆的一层封装，因此，优先队列的实现，只需要将堆的实现代码封装起来，对外提供插入、删除、获取堆顶元素等操作即可。

以大顶堆为例：初始化时
令n=-1，表示当前队列为空；可以增加capacity，表示当前队列的容量,初始化时改为new[capacity]；此外还要增加是否需要扩容等操作，这里就不在作额外实现，只实现主要功能。

struct PriorityQueue
{
    int* arr;
    int n;
    PriorityQueue(int* arr,int n);
    void Push(int val);
    void Pop();
    int Top();
};

PriorityQueue::PriorityQueue(int* arr,int n)
{   
    arr=new int[n];
    for(int i=0;i<n;i++){
        arr[i]=arr[i];
    }
    for(int i=n/2-1;i>=0;i--){
        Heapify(arr,n,i);
    }
}

void PriorityQueue::Push(int val)
{
    n++;
    arr[n] = val;
    Heapify(arr,n/2,0);
}

void PriorityQueue::Pop()
{
    swap(arr[0],arr[n]);
    n--;
    Heapify(arr,n/2,0);
}

int PriorityQueue::Top()
{
    return arr[0];
}

本文作者： KongXinQing
本文链接： https://13114987559.github.io/2023/09/23/note/数据结构与算法-堆与优先队列/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！