Building MaxHeap Largest Не отправлено в начало

Question

Я пытаюсь построить максимальную кучу из вектора размера 10. Он содержит числа 1-10. Тем не менее моя программа не будет устанавливать наибольшее значение 10 для самой большой переменной, потому что при сравнении она превышает диапазон моего вектора.

if ((l <= v.size()) && (v.at(l) > v.at(i))) 
    {largest = l;} 
    else { largest = i; } 

    if ((r <= v.size()) && (v.at(r) > v.at(largest))) // r at some point is 10. which exceeds v. 
    {largest = r;} 

Я попытался установить, если заявление вокруг выше, что код будет поймать ошибку, но затем я получаю это:

INPUT: 1 2 3 4 5 6 7 8 9 10 
OUTPUT: 9 8 7 4 5 6 3 2 1 10 

Что почти правильно, но 10 должна быть первой. Что я могу сделать, чтобы убедиться, что куча построена правильно? Вот мой полный код:

#include <iostream> 
#include <fstream> 
#include <string> 
#include <vector> 

using namespace std; 


vector<string> readFile(string fileName) { /* read in file. Works Fine.*/} 
void display(vector<string>& v) {/*displays vector. works fine. */ } 

inline int parent(int i){return i/2; } 
inline int left(int i) {return 2*i;} 
inline int right(int i) {return 2*i + 1;} 

void Max_Heapify(vector<string>& v, int i) 
{ 
    int largest; 
    int l = left(i); 
    int r = right(i); 
    i--; 

    if ((l <= v.size()) && (v.at(l) > v.at(i))) 
    {largest = l;} 
    else { largest = i; } 

    if ((r <= v.size()) && (v.at(r) > v.at(largest))) 
    { 
     largest = r; 
    } 

    if (largest != i) 
    { 
     string temp = v.at(i); 
     v.at(i) = v.at(largest); 
     v.at(largest) = temp; 

     Max_Heapify(v, largest); 
    } 
} 

void Build_Max_Heap(vector<string>& v, int length) 
{ 
    for (int i = (length/2); i > 0; i--) 
    { 
     Max_Heapify(v, i); 
    } 
} 

int main() { 
    vector<string> vectorReadIn; 
    vector<string> sortedVector; 
    int x = 0; 

    string fileName = "C:/Users/user/Downloads/Algorithims/Perm Words/perm15k.txt"; 

    vectorReadIn = readFile(fileName); 

    cout << "Unsorted file:" << endl; 
    display(vectorReadIn); 
    vectorReadIn.resize(vectorReadIn.size()); 
    Build_Max_Heap(vectorReadIn, vectorReadIn.size()); 

    display(vectorReadIn); 
} 

Answer 1

В дополнение к комментарию Игоря Тандетника, ваши расчеты для левого и правого ребенка ошибочны. В векторе с индексом 0 является первым элементом, корень вашей кучи индекса 0. Таким образом, расчеты для левого и правого ребенка являются:

left child: (2*x) + 1 
right child: (2*x) + 2 

Расчетов у вас есть это для кучи с корнем индекс 1.

Кроме того, цикл в вашей Build_Max_Heap функции должно быть:

for (int i = (length/2); i >= 0; i--) 

То есть, вы должны проверить, чтобы увидеть, если первый элемент в векторе должен быть изменен.