如何使用C++实现堆数据结构 |21xrx.com

如何使用C++实现堆数据结构

2023-07-05 20:53:06 深夜i -- --

C++ 堆实现数据结构优先队列

堆是一种非常常用的数据结构，它通过树形结构来存储和管理数据。堆的一个主要应用是优先队列，但它也可以用于排序和搜索等应用程序。在C++中，实现堆数据结构是非常方便的，可以使用STL中的堆容器，也可以从头开始实现自己的堆。

一、STL中的堆容器

在C++ STL中，有一个堆容器，即priority_queue。priority_queue是模板容器，它基于vector来实现堆数据结构。可以使用以下代码来定义一个堆：


#include <queue> //头文件
using namespace std;
priority_queue<int> pq; //定义一个堆

在上面的代码中，priority_queue是C++ STL中的堆容器，int是堆中元素的类型。

1. 将元素插入到堆中

可以使用以下代码将元素插入堆中：


pq.push(3); //元素3被插入到堆中
pq.push(5); //元素5被插入到堆中
pq.push(1); //元素1被插入到堆中

2. 获取堆顶元素

可以使用以下代码获取堆顶元素：


int top_element = pq.top(); //获取堆顶元素
cout << top_element << endl; //打印堆顶元素

3. 弹出堆顶元素

可以使用以下代码弹出堆顶元素：


pq.pop(); //弹出堆顶元素

二、自己实现堆

如果想要从头开始实现堆，可以使用数组来存储堆中的元素，并使用以下公式计算子节点和父节点的下标：

- 父节点的下标为 i/2

- 左子节点的下标为 2i

- 右子节点的下标为 2i+1

可以使用以下代码来实现堆：


#include <iostream>
using namespace std;
#define MAX_HEAP_SIZE 100
class Heap {
  private:
    int* A;
    int size;
    int heapSize;
  public:
    Heap(){
      A = new int[MAX_HEAP_SIZE];
      size = MAX_HEAP_SIZE;
      heapSize = 0;
    }
    
    void heapify(int i){
      int l,r,largest;
      
      l = left(i);
      r = right(i);
      
      if(l<=heapSize && A[l]>A[i])
        largest = l;
      else largest = i;
      
      if(r<=heapSize && A[r]>A[largest])
        largest = r;
        
      if(largest != i)
      {
        swap(A[i],A[largest]);
        heapify(largest);
      }
    }
    
    int parent(int i)
      return i/2;
    
    
    int left(int i){
      return 2*i;
    }
    
    int right(int i){
      return 2*i+1;
    }
    
    int maximum(){
      return A[1];
    }
    
    void insert(int key)
    {
      heapSize ++;
      A[heapSize] = key;
      int i = heapSize;
      
      while(i>1 && A[parent(i)]<A[i])
      {
        swap(A[i],A[parent(i)]);
        i = parent(i);
      }
    }
    
    void pop_max()
    {
      if(heapSize<1)
        return;
      swap(A[1],A[heapSize]);
      heapSize--;
      heapify(1);
    }
};
int main()
{
  Heap h;
  h.insert(12);
  h.insert(7);
  h.insert(15);
  h.insert(3);
  
  cout<<(h.maximum())<<endl;
  
  h.pop_max();
  
  cout<<(h.maximum())<<endl;
  
  h.pop_max();
  
  cout<<(h.maximum())<<endl;
  return 0;
}

在上面的代码中，我们创建了一个Heap类，并实现了heapify、parent、left、right、maximum、insert和pop_max等函数。heapify函数用于将节点恢复到堆的状态，parent、left和right函数用于计算节点和其子节点的位置，maximum函数返回堆中元素的最大值，insert函数用于向堆中插入元素，pop_max函数用于弹出堆中的最大元素。

上一篇: idea打包java可执行jar包

下一篇: 用C++计算时间过去的百分比

评论区

()

相似文章