Я правильно реализую алгоритм "Heapify"?

Ответ 1

Ваш алгоритм работает. Проблема заключается в переводе алгоритма в код. Скажем, вы объявили Data как:

int Data[7];

и вы заполняете его начальными значениями {0, 1, 2, 3, 4, 5, 6}. Предполагая определения LeftChild(i) и RightChild(i) как-то вроде:

#define LeftChild(i) ((i << 1) + 1)
#define RightChild(i) ((i << 1) + 2)

то ваша функция BuildHeap(), которая должна быть чем-то вроде:

void Heap::BuildHeap()
{
    for(int i = (7 >> 1); i >= 1; i--) // in general, replace 7 with 
                                       // (sizeof(Data)/sizeof(int)), presuming 
                                       // you have an array of int's. if not, 
                                       // replace int with the relevant data type
    Heapify(i-1);
}

начнет процесс Heapify в корне нижнего правого корня. В этом случае это индекс массива 2 с левым дочерним элементом 5 и правым дочерним элементом 6. Heapify будет правильно обмениваться 2 и 6 и рекурсивно вызывать Heapify(6).

Здесь все может зацепиться! В настоящее время ваше дерево выглядит следующим образом:

                         0
                    1         2
                 3     4   5     6
            u n d e f i n e d  s p a c e

так что вызов Heapify(6) будет покорно сравнивать значения Data[6] с Data[13] и Data[14] (опасностями С++ и отсутствием соблюдения границ границ массива, в отличие от Java). Очевидно, что последние два значения могут быть любыми барахлами, оставшимися в ОЗУ. Одним из решений здесь, уродливым, но рабочим патчем, является добавление 8 элементов в объявление данных и их инициализация до некоторого значения ниже любого элемента массива. Лучшее решение - добавить переменную heapSize в ваш класс и установить ее равной длине вашего массива:

heapSize = (sizeof(Data)/sizeof(int));

Затем интегрируйте логику только для сравнения дочерних узлов, если они являются допустимыми листьями дерева. Эффективная реализация этого:

void Heap::Heapify(int i)
{
    int temp, l, r, heapify;

    l = LeftChild(i); // get the left child
    r = RightChild(i); // get the right child

    if((l <= heapSize) && (Data[l] > Data[i]))
        heapify = l;
    else heapfiy = i;
    if((r <= heapSize) && (Data[r] > Data[heapify]))
        heapify = r;
    if(heapify != i) // one of the two child nodes has proved 
                     // larger than Data[i], so interchange values
    {
        //swap parent with left child
        temp = Data[i];
        Data[i] = Data[heapify];
        Data[heapify] = temp;

        Heapify(heapify);
    }
}

Итак, чтобы обобщить, решение так же просто, как добавление логики, чтобы убедиться, что дочерние узлы являются допустимыми листьями дерева, а ваша основная функция будет иметь что-то вроде:

Heap heap;

// initialize Data here    

heap.BuildHeap();

Надеюсь, что это поможет.

Ответ 2

Нет. На дереве

      1
     / \
    /   \
   /     \
  2       3
 / \     / \
6   7   4   5

вывод будет

      3
     / \
    /   \
   /     \
  2       5
 / \     / \
6   7   4   1

который имеет несколько нарушений кучи. (Я предполагаю, что Data[l] и Data[r] минус бесконечность, если соответствующие дети не существуют. Для этого может потребоваться дополнительная логика.)

Что делает ваша функция, это исправить дерево, которое не может быть кучей, но левые и правые поддеревья - это кучи. Вы должны называть его на каждом node в postorder (т.е. Для я от n - 1 до 0), так что дети из я являются кучками при вызове Heapify (i).

Ответ 3

Теперь ваш код успешно создает кучу. Был только один концептуальный недостаток: остальные были ошибочными ошибками индексации. Одна фундаментальная ошибка была в BuildHeap: у вас был

for(int i = heapSize; i >= 1; i--)
{
    Heapify(i-1);
}

тогда как это должно быть

for(int i = (heapSize / 2); i >= 1; i--)
{
    Heapify(i-1);
}

Это действительно важно, вы должны увидеть, что Heapify всегда вызывается в корне дерева, и (это действительно круто) вы можете легко найти последний корневой корень в массиве в индексе ((heapSize/2) - 1 ) (это для С++ и Java-стиля, где первый индекс == 0). То, как было написано ваш код под названием Heapify на последнем листе дерева, который ошибочен.

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

Ваш заголовочный файл:

#ifndef HEAP_H
#define HEAP_H
//Programmer: Christopher De Bow
//Date: november 15, 2011

class Heap
{
private:
    int Data [100];
    int Parent(int);
    int RightChild(int);
    int LeftChild(int);
    void Heapify(int);
    void BuildHeap();
// SO added heapSize
    int heapSize;

public:
    Heap();
    void insert();
    void HeapSort();
    void ExtractMaximum();
    int Maximum();
    void PrintHeap();
    int heapsize;
    void SetData(int[]);
};

#endif

Ваш файл cpp:

#include <iostream>
#include "Heap.h"
using namespace std;
//Programmer: Christopher De Bow
//Date: november 15, 2011

Heap::Heap()
{
    int init [10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    heapSize = 10;
    SetData(init);
}

int Heap::Parent(int index)
{
    int Rval;
    if(index%2 == 0)// if the index is even
    {
        Rval = ((index-1)/2);
    }
    else// if the index is odd
    {
        Rval = (index/2);
    }
    return Rval;
}

int Heap::RightChild(int arrplace)
{
    int ret;
    ret = ((2*arrplace)+2); //rightchild is index times 2 plus 2
    return ret;
}

int Heap::LeftChild(int i)
{
    int rval;
    rval = ((2*i)+1); //leftchild is index times 2 plus 1
    return rval;
}

void Heap::Heapify(int i)
{
    int temp, l, r, heapify;

    l = LeftChild(i); // get the left child
    r = RightChild(i); // get the right child

// you have to compare the index to (heapSize - 1) because we are working
// with C++ and the first array index is 0 : l and r are direct indices
// into the array, so the maximum possible index is the heapSize'th 
// element, which is at heapSize-1. this was kind of nasty as it let the 
// heapify index get too large and led to a swap with memory beyond the
// last element of the array (again, C++ doesn't enforce array boundaries
// as Java does).
    if((l <= (heapSize-1)) && (Data[l] > Data[i]))
        heapify = l;
    else
        heapify = i;
// you have to compare the index to (heapSize - 1) because we are working
// with C++ and the first array index is 0 : l and r are direct indices
// into the array, so the maximum possible index is the heapSize'th 
// element, which is at heapSize-1. this was kind of nasty as it let the 
// heapify index get too large and led to a swap with memory beyond the
// last element of the array (again, C++ doesn't enforce array boundaries
// as Java does).
    if((r <= (heapSize-1)) && (Data[r] > Data[heapify]))
        heapify = r;
    if(heapify != i) // one of the two child nodes has proved
    {                // larger than Data[i], so interchange values
        //swap parent with left child
        temp = Data[i];
        Data[i] = Data[heapify];
        Data[heapify] = temp;
        Heapify(heapify);
    }
}

void Heap::BuildHeap()
{
    // we do not have a heap
    // we will make a heap
    // by calling heapify starting at the lowest
    // internal node in the heap
// i must be initialized to (heapsize/2), please see my 
// post for an explanation
    for(int i = heapSize/2; i >= 1; i--)
    {
        Heapify(i-1);
    }
}

void Heap::insert()
{
    int insert;
    heapSize = (heapSize + 1);
    //getting data from the user
    cout<<"what data would you like to insert?"<<endl;
    cin>>insert;
    Data[heapSize] = insert;
    BuildHeap(); //call BuildHeap on array
    cout<<"done"<<endl;
}

void Heap::PrintHeap()
{
    BuildHeap();
// the array indices are from 0 through (heapSize-1), so 
// count must be less than _or equal to_ (heapSize-1). another
// way of phrasing this (which i applied in this function)
// is (count < heapSize). you'll get better boundary conditions
// with practice.
    for(int count = 0; count < heapSize; count++)
    {
// added an endl to the output for clarity
        cout << Data[count] << endl;// print out every element in heap
    }
    cout<<endl<<endl;
}

void Heap::HeapSort()
{
    BuildHeap();
    int temp;
    // do this for every elem in heap:
    for(int i = 0; i < heapSize; i++)
    {
        temp = Data[heapSize-1];
        Data[heapSize-1] = Data[0];
        Data[0] = temp;
        heapSize--;
        BuildHeap();
    }
    PrintHeap();
}

void Heap::ExtractMaximum()
{
    BuildHeap();
    //assign last thing in heap to first thing in heap
    Data[0] = Data[heapSize];
    heapSize--; // decrease heapSize by one
    Heapify(0); // heapify from the top
}

int Heap::Maximum()
{
    int Rval;
    BuildHeap();// make sure we have a heap
    Rval = Data[0];
    return Rval; // return top thing
}

//initialize the elements in the "Data" array
void Heap::SetData(int x[])
{
// the array indices are from 0 through (heapSize-1), so 
// count must be less than _or equal to_ (heapSize-1). another
// way of phrasing this (which i applied in this function)
// is (i < heapSize). you'll get better boundary conditions
// with practice.
    for(int i = 0; i < heapSize; i++)
    {
        Data[i] = x[i];
    }
}

// basic confirmation function
int main()
{
    Heap heap;
    heap.PrintHeap();

    return 0;
}

Ответ 4

Ваш код, как написано здесь, кажется правильным; но нет ничего подобного написанию нескольких тестовых примеров, чтобы увидеть, как это работает. Обязательно проверяйте кучу с помощью 1, 2, 3, 4 и десятков элементов. (Я ожидаю, что базовый футляр будет там, где этот фрагмент будет коротким - как он справится, когда i не имеет детей?) Тестирование на небольших кучах должно проявляться в спешке.)

Небольшой совет для этой части:

if(Data[l] > Data[r])
{
    //swap parent with left child
    temp = Data[i];
    Data[i] = Data[l];
    Data[l] = temp;
    heapify = l; // index that was swapped
}
//if right is the bigger child
else
    { //swap parent with right child
    temp = Data[i];
    Data[i] = Data[r];
    Data[r] = temp;
    heapify = r; // index that was swapped
}

Вероятно, вы можете получить четкость, указав только индекс в блоках if:

if(Data[l] > Data[r]) {
    swapme = l;
} else {
    swapme = r;
}

temp = Data[i];
Data[i] = Data[swapme];
Data[swapme] = temp;
heapify = swapme;