21xrx.com
2024-11-05 16:24:43 Tuesday
登录
文章检索 我的文章 写文章
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']}}
()
回复
回复