Алгоритм минимальной кучи

Question

Это мой алгоритм minHeap, однако он не работает должным образом:

public static int [] fixheap(int heap[], int n, int i){
    int j=2*i;
    int weight = heap[i];

    while (j<=n){
        if((j<n) && heap[j] > heap[j+1])
            j++;
        if(weight <= heap[j]) break;
        else 
        heap[j/2] = heap[j]; 

        j=j*2;
    }

    heap[j/2]= weight;

    return heap;
}

public static void makeheap(int heap[], int n){

    for (int i=n/2; i>=0; i--){
        fixheap(heap, n ,i);
    }   
}

Когда элементы данных добавляются в разных порядках, алгоритм возвращает неправильные значения minHeaps. Кто-нибудь может увидеть какие-либо очевидные проблемы для этого алгоритма минимальной кучи?

Answer 1

Вы сравниваете неправильные элементы массива для формирования кучи.Попробуйте запустить программу «всухую»

Поскольку массив начинается с индекса 0, вы должны сначала взять i = n / 2-1.

public static void makeheap(int heap[], int n){

     for (int i=n/2 - 1; i>=0; i--){
     fixheap(heap, n ,i);
    }   
}

И затем вам придется изменитьВаша функция исправления, чтобы получить правильное значение для j

j = i * 2 + 1

Answer 2

Следующий код написан на python, но я выделю строки, которые делают тяжелую работу, и в процессе, надеюсь, представлю другое решение создания min-heap

heapArray = []  
for heapKey in someArray:
    insert(heapArray, int(heapKey))
return heapArray;

def insert(heapArray, heapKey):
  heapArray.append(heapKey)
  index_of_key = len(heapArray)-1
  parent_index_of_key = (index_of_heap_key-1)/2
  while index_of_key>0:
    if(heapKey < heapArray[parent_index_of_key]):
        __swap(index_of_key, parent_index_of_key, heapArray)
        index_of_key = parent_index_of_key;
        parent_index_of_key = (index_of_key-1)/2
    else:
        break # we have reached the right spot

В приведенном выше примере мы воссоздаем кучу (да, это означает больше памяти, но для иллюстрации это может быть хорошим началом). Когда мы создаем кучу, мы просто проверяем значение вновь вставленного ключа с его родителем (через parent_index_of_key).

Если родительский элемент больше, чем его дочерний элемент, то мы меняем значение и обновляем индексы (как для замененного ключа, так и для его нового родительского элемента). Мы повторяем этот процесс, пока не достигнем вершины кучи или если ключ кучи не может идти дальше по цепочке

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

Answer 3

Я считаю, что способ, которым вы находите родителя и / или детей, неверен.

Подумайте об этом, если левые дети находятся на index1, а правые на index2, как мне это сделать?добраться до своих родителей в index0?

А как насчет поиска index0 детей (index1 и index2)?