C++实现二进制堆

在C++中，实现二进制堆的方法如下：

首先，定义一个二进制堆类，包含以下成员变量：

一个std::vector<int>类型的数组，用于存储堆中的元素
一个int类型的变量，表示堆中元素的数量

然后，实现以下成员函数：

insert(int value)：向堆中插入一个元素
extract_min()：从堆中取出最小元素
decrease_key(int index, int value)：将指定位置的元素值减小
get_min()：获取堆中最小元素

下面是一个简单的实现：

#include<iostream>
#include<vector>

class BinaryHeap {
public:
    BinaryHeap() : size_(0) {}

    void insert(int value) {
        heap_.push_back(value);
        size_++;
        heapify_up(size_ - 1);
    }

    int extract_min() {
        if (size_ == 0) {
            return -1;
        }
        int min_value = heap_[0];
        heap_[0] = heap_[size_ - 1];
        size_--;
        heapify_down(0);
        return min_value;
    }

    void decrease_key(int index, int value) {
        heap_[index] = value;
        heapify_up(index);
    }

    int get_min() {
        if (size_ == 0) {
            return -1;
        }
        return heap_[0];
    }

private:
    void heapify_up(int index) {
        while (index > 0 && heap_[parent(index)] > heap_[index]) {
            std::swap(heap_[index], heap_[parent(index)]);
            index = parent(index);
        }
    }

    void heapify_down(int index) {
        int min_index = index;
        while (2 * index + 1< size_) {
            min_index = 2 * index + 1;
            if (min_index + 1< size_ && heap_[min_index] > heap_[min_index + 1]) {
                min_index++;
            }
            if (heap_[index] <= heap_[min_index]) {
                break;
            }
            std::swap(heap_[index], heap_[min_index]);
            index = min_index;
        }
    }

    int parent(int index) {
        return (index - 1) / 2;
    }

private:
    std::vector<int> heap_;
    int size_;
};

这个实现中，heapify_up()和heapify_down()函数分别用于在插入和删除元素时维护堆的性质。parent()函数用于获取指定节点的父节点的索引。