21xrx.com
2024-11-22 08:00:29 Friday
登录
文章检索 我的文章 写文章
C++实现大根堆结构体
2023-07-02 09:41:32 深夜i     --     --
C++ 大根堆 结构体 优先队列 堆排序

大根堆是一种常见的数据结构,在许多算法问题中经常用到。它通常由一个数组来实现,其中父节点的值总是大于或等于其子节点的值。

在C++中,可以使用结构体来实现大根堆。下面是一个示例代码:


#include <iostream>

using namespace std;

const int MAX_N = 100;

struct Heap {

  int a[MAX_N];

  int size;

  void push(int x) {

    a[size] = x;

    int i = size++;

    while (i > 0) {

      int p = (i - 1) / 2;

      if (a[p] >= x) break;

      a[i] = a[p];

      i = p;

    }

    a[i] = x;

  }

  int pop() {

    int res = a[0];

    int x = a[--size];

    int i = 0;

    while (i * 2 + 1 < size) {

      int a = i * 2 + 1, b = i * 2 + 2;

      if (b < size && a[i] < a[b]) a = b;

      if (a[i] >= a[x]) break;

      a[i] = a[x];

      i = x;

    }

    a[i] = x;

    return res;

  }

};

int main() {

  Heap h;

  h.push(5);

  h.push(8);

  h.push(2);

  h.push(3);

  cout << h.pop() << endl; // 输出8

  cout << h.pop() << endl; // 输出5

  return 0;

}

在上面的代码中,结构体Heap包含一个数组a和一个整数size,表示当前堆中的元素数量。当我们添加一个新元素时,我们从底部开始将其向上冒泡直到正确的位置。当我们弹出堆顶元素时,我们取出最后一个元素放在顶部,然后向下沉降直到找到正确的位置。

这个实现有一个限制,最大堆的大小是MAX_N,如果我们需要更大的堆,需要将MAX_N设置为更大的值。此外,push和pop的时间复杂度都是O(logn),其中n是堆中的元素数量。

总之,在C++中实现大根堆结构体是非常简单的,这种数据结构在许多算法中都是必须的,因此在编程比赛或其他编程任务中需要掌握。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复