C++实现二进制堆

#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_;
};