如何修复最小堆插入/提取函数中的错误？

Question

我这样编译：

clang++ -std=c++11 test.cpp MinHeap.cpp -o test

执行失败 test2“断言失败：(array[i] == i)，函数 test2，文件 test.cpp，行 ... 中止陷阱：6”。test2 正在创建一个大小为 10000 的数组（整数从 0 到 10000 随机排列）并使用 heapsort 和 MinHeap class 对其进行排序。

100% heapsort 已正确实施。我已经完成了主要 MinHeap 函数的逻辑（插入 -> bubble_up ，提取 -> bubble_down）但找不到错误。

test.cpp

#include <cassert>
#include <cstdlib>

#include "MinHeap.hpp"

#include <iostream>

void heapsort(int* const array, int size){
  MinHeap heap;

  for (int i = 0; i < size; i++){
    heap.insert(array[i]);
  }

  for (int i = 0; i < size; i++){
    array[i] = heap.extractMin();
  }
}

void test2(){
  int size = 10000;
  int* array = new int[size];
  for(int i = 0; i < size; i++){
    array[i] = i;
  }

  unsigned int seed = 2019;
  std::srand(seed);
  for(int i = 0; i < size; i++){
    int index1 = std::rand() % size;
    int index2 = std::rand() % size;

    int number1 = array[index1];
    array[index1] = array[index2];
    array[index2] = number1;
  }

  heapsort(array, size);

  for(int i = 0; i < size; i++){
    assert(array[i] == i);
  }

  delete [] array;
}

int main(){
  insert_test();
  extract_test();
  test2();
  return 0;
}

MinHeap.hpp

#ifndef MINHEAP_HPP
#define MINHEAP_HPP

class MinHeap{
public:
  MinHeap();
  //  MinHeap(const MinHeap& other);
  //  MinHeap& operator=(const MinHeap& other);
  ~MinHeap();

  void insert(int number);
  int extractMin();
  bool isEmpty() const;
  void toString() const;

private:
  void swap(int &a, int &b);
  void expand();
  void bubble_up(int start);
  void bubble_down(int start);
  void fit();
  int find_min(int a, int b, int c);

  int* array;
  int size;
  int capacity;
};

#endif

MinHeap.cpp

#include "MinHeap.hpp"
#include <string>
#include <iostream>

MinHeap::MinHeap(){
    size = 0;
    capacity = 10000;
    array = new int[capacity];
}

MinHeap::~MinHeap(){
    delete[] array;
}

void MinHeap::insert(int number){
    if(isEmpty()){
        array[0] = number;
        size++;
        return;
    }
    if (size == capacity){
        throw std::runtime_error("Overflow, int not inserted")
    }

    array[size] = number;
    bubble_up(size);
    size++;

    return;

}

void MinHeap::swap(int &a, int &b){
    int hold = a;
    a = b;
    b = hold;
}

int MinHeap::extractMin(){
    if(isEmpty()){
        throw std::runtime_error("Not Valid");
    }
    else if (size == 1){
        size--;
        return array[0];
    }

    int min = array[0];
    array[0] = array[size-1];
    size--;
    bubble_down(0);

    return min;
}

void MinHeap::bubble_up(int start){
    int child = start;
    int parent = (child - 1)/2;

    if (start == 1){
        if (array[0] > array[1]){
            swap(array[0], array[1]);
        }
    }

    while (parent >= 0 and array[child] < array[parent]){
        swap(array[child], array[parent]);
        child = parent;
        parent = (child - 1)/2;
    }
}

void MinHeap::bubble_down(int start){
    int parent = start;
    int left = (2*parent)+1;
    int right = (2*parent)+2;

    if (left > size){
        if(array[parent] < array[right]){
                swap(array[parent], array[right]);
            }
            return;
    }
    if (right > size){
        if(array[parent] < array[left]){
                swap(array[parent], array[left]);
            }
            return;
    }

    int min = find_min(array[parent], array[left], array[right]);

    if (min == array[left]){
        swap(array[left], array[parent]);
        bubble_down(left);
    }
    else if (min == array[right]){
        swap(array[right], array[parent]);
        bubble_down(right);
    }
    return;
}

int MinHeap::find_min(int a, int b, int c){
    if (a < b and a < c){
        return a;
    }
    else if (b < a and b < c){
        return b;
    }
    return c;
}

bool MinHeap::isEmpty() const{
    if (size > 0){
        return false;
    }
    return true;
}

Answer 1

看起来像最后一个运行通过在bubble_down函数中parent为9466时，数组越界，因为限制是10,000，你正在尝试比较正确值为 (2 * parent) + 2，得到 18,934。我不确定您要完成什么，但我认为这就是错误所在。

if (left > size) {
    if (array[parent] < array[right]) { // Breaking here!
        swap(array[parent], array[right]);
    }
    return;
}

如何修复最小堆插入/提取函数中的错误？

How to fix bug in min heap insertion / extract functions?

c++

sorting

c++11

minmax-heap