Как исправить ошибку в функциях ввода / извлечения минимальной кучи?

Question

Я компилирую так:

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

Реализация не выполнена test2 " Утверждение не выполнено: (массив [i] == i), функция test2, файл test.cpp, строка ... Прерывание прерывания: 6". Test2 создает массив размером 10000 (с целочисленными значениями от 0 до 10000) и использует сортировку по типу heapsort и класс MinHeap для сортировки по порядку.

100% heapsort реализован правильно. Я прошел логику основных функций MinHeap (insert -> bubble_up, extract -> 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 равен 9466, массив выходит за границы, поскольку предел равен 10000, и вы пытаетесь сравнить правильное значение как (2 * parent) + 2 что дает вам 18 934 Я не совсем уверен, чего вы пытаетесь достичь, но я думаю, что именно в этом и заключается ошибка.

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