массив кучи - удалить корень

Question

Я немного смущен о кучах. У меня есть целочисленный массив как реализация минимальной кучи. Как вы можете вычислить шаги барботажа при удалении элемента min из корня. Что еще более важно, скажем, у вас есть

  3 
     5  5 
    7 8  

Если вы удалите 3, то вам придется заменить его на 8 и спуститься вниз. Однако, поскольку оба корневых ребенка имеют равное значение (5), то каким образом он будет пузыриться (справа от левой)? Это важно, так как количество шагов, чтобы привести его в порядок, будет отличаться.

Thanks

Answer 1

Я думаю, что это действительно зависит от реализации вашего алгоритма. Удаление первого элемента часто используется в алгоритме сортировки кучи. Вы берете первый элемент и помещаете последний элемент на свое место. Затем вы вызываете heapify() на корень, который решает, каким путем сбрасываться.

void heapify(int index) { 

     int l = getLeft(index); 
     int r = getRight(index); 
     int largest; 

     if(l <= storage.length && storage[index] < storage[l]){ 
      largest = l; 
     } else { 
      largest = index; 
     } 

     if(r <= storage.length && storage[largest] < storage[r]){ 
      largest = r; 
     } 

     if(largest != index){ 
      storage.swap(index, largest); 
      heapify(largest); 
     } 

    } 

Вы можете увидеть, что она занимает самый большой из своих детей, поменять себя и самый большой, и держать пузырясь, где самый большой был. В этой реализации, если правая и левая равны, она будет перемещаться по левому поддереву.

Время работы heapify() на поддереве размера n - это O (1), чтобы найти самый большой элемент + время выполнения рекурсивного heapify в поддереве - каждое поддерево имеет размер не более 2n/3, худший случай возникает, когда нижний уровень дерева точно наполовину заполнен.

Поэтому время работы heapify может быть описано как:

T(n) = T(2n/3) + O(1)

Мастер теорема получает, что:

T(n) = O(lg n)