# 由堆排序引出的最小堆 ## 堆排序 ~~~ /** * 堆化 */ void heapify(vector<int>& data, int i, int n) {    int max = i;    int left = i * 2 + 1;    int right = i * 2 + 2;    if (left < n && data[max] < data[left]) {        max = left;   }    if (right < n && data[max] < data[right]) {        max = right;   }    if (max != i) {        swap(data[i], data[max]);        heapify(data, max, n);   } } ​ /** * 构建堆 */ void build_heap(vector<int>& data) {    int n = data.size();    int last_node = n - 1; ​    for (int i = (last_node - 1) / 2; i >= 0; i--) {        heapify(data, i, n);   } } ​ /** * 堆排序 *   parent = (i - 1) / 2 *   left = i * 2 + 1 *   right = i * 2 + 2 */ void heap_sort(vector<int>& data) {    build_heap(data);    for (int i = data.size() - 1; i > 0; i--) {        swap(data[0], data[i]);        heapify(data, 0, i);   } } ~~~ ## 最小堆 ~~~ class minHeap { public:    minHeap(size_t capacity)   : capacity_(capacity),      count_(0),      data_(capacity)   {} ​    bool emepty() const { return count_ == 0; } ​    void insert(int value) {        if (count_ < capacity_) {            data_[count_++] = value;            heapify_up(data_, count_ - 1);       } else {            // 最大堆主要保存所有数据容量内最大的数据            if (value > data_[0]) {                data_[0] = value;                heapify_down(data_, 0);           }       }   } ​    int pop() {        assert(count_ > 0);        int result = data_[0];        data_[0] = data_[--count_];        heapify_down(data_, 0);        return result;   } ​ private:    void heapify_down(vector<int>& data, size_t index) {        int min = index;        int left = index * 2 + 1;        int right = index * 2 + 2;        if (left < count_ && data[left] < data[min]) {            min = left;       }        if (right < count_ && data[right] < data[min]) {            min = right;       }        if (min != index) {            swap(data[index], data[min]);            heapify_down(data, min);       }   } ​    void heapify_up(vector<int>& data, size_t index) {        if (index == 0)            return;        int parent = (index - 1) / 2;        if (data[parent] > data[index]) {            swap(data[parent], data[index]);            heapify_up(data, parent);       }   } ​ private:    vector<int> data_;    size_t capacity_;    size_t count_; }; ~~~