Реализация связанного списка Binary Min Heap (возникают проблемы с манипуляциями ...)

Question

Так что я пытаюсь реализовать двоичную мин кучу. Я понимаю, что влечет двоичная минимальная куча с точки зрения ее структуры и ее свойств. Однако я пытаюсь реализовать стену, используя указатели и узлы.

Я использую Node, который имеет right/left and pointers, int element и parent pointer. У меня также есть LastNode на месте, которое указывает на последний вставленный узел.

Моя ссора в том, что я не знаю, что делать, когда вставляю элемент в терминах последнего Узла. Вот что я имею в виду.

Шаг 1.) Предположим, что куча пуста, поэтому вы создаете root, а именно x, где x содержит элемент, и вы устанавливаете root.left/right = null и LastNode = root.left.

  X
 / \
0   0

Это та часть, где я застрял. Я знаю, что когда вы создаете другой узел для хранения другого элемента, он будет находиться слева от X или там, куда указывает LastNode. Мои вопросы, что мне делать дальше с LastNode, я указываю это на x.right? Я пытаюсь держать insert(int x) запущенным в logN, и манипулирование lastNode будет становиться все длиннее и интенсивнее на каждом уровне.

Может кто-нибудь сломать? Спасибо

Answer 1

Поскольку вы должны вставить узлы на нижнем уровне, то есть в ширину, что если вы ведете запись всех узлов, вставленных до сих пор в очередь?Когда вы вставляете новый узел в кучу, найдите последнюю позицию в очереди и вставьте туда данные.Затем heapify_up этого узла.

Answer 2

Ну, вам нужно вставить элемент на последнем уровне кучи, а затем выяснить, нужно ли всплывать. Таким образом, вам нужен указатель lastNode, чтобы указать не последний вставленный элемент (он вполне может быть последним добавленным, но он мог бы пройти весь путь, будучи теперь корневым; это совсем не полезно), а скорее родительский элемент где вы будете вставлять этот новый элемент. Это помогает?

(Позднее редактирование): есть более оптимальный способ построения кучи, но я чувствую, что сейчас это не то, что вам нужно, поэтому я предположил, что вы будете использовать простую вставку с помощью O (log n) за каждый новый элемент.

Answer 3

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

Например, допустим, вы хотите разместить новый узел в следующем дереве:

    A
   / \
  B   C
 / \ / \
D  E X  X

Начиная сверху, вы обнаружите, что внизу находятся 2/4 полных узла. Поэтому вы спускаетесь через правую ветку и попадаете на вершину дерева с корнем C. В нижней части этого дерева находятся 0/2 полных узлов, поэтому вы спускаетесь через левую ветвь и попадаете в листовой узел, где вы размещаете новый элемент.

Вот код Java, который я использовал для вычисления высоты дерева, количества возможных узлов в нижней части дерева с любой заданной высотой и количества полных или «используемых» узлов в нижней части дерева. с размером size.

private int height(int size) {
    return (int) Math.ceil(log2(size + 1));
}
// returns the amount of space in the bottom row of a binary tree
private int bottomRowSpace(int height) {
    return (int) Math.pow(2, height - 1);
}
// returns the amount of filled spots in the bottom row of a binary tree
private int bottomRowFilled(int size) {
    return size - (bottomRowSpace(height(size)) - 1);
}
// log base2
private double log2(double a) {
    return Math.log(a) / Math.log(2);
}

Answer 4

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

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

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

Обновление: вот код (https://gist.github.com/naveenwashere/5607516):

public class BinaryHeap {

//Later you can implement a resizable array logic.
int[] bH;

public BinaryHeap(int N)
{
    bH = new int[N + 1];
}

//Index of the root
int k = 1;

//The APIs
public void put(int key)
{
    //Place the element at the end of the array
    bH[this.k] = key;       
    if(bH[this.k] > bH[this.k/2])
    {
        //since the elements in an array implementation of the binary heap is put at the end of the array,
        //we must always check if the property of the tree holds true or not.
        swim(this.k);
    }
    this.k++;
}

public void deleteMax()
{
    //Replace the element in the root with the element at the end of the array
    bH[1] = bH[k];
    //Restore the order of the tree
    sink(1);
    this.k--;
}

public void deleteMin()
{
    bH[this.k - 1] = 0;
    this.k--;
}

public void swim(int k)
{
    while((k != 1) && (bH[k] > bH[k/2]))
    {
        swap(k, k/2);
        k = k/2;
    }
}

public void sink(int k)
{
    while(2*k <= this.k)
    {
        int j = 2*k;
        if(max(j, j+1)) j++;
        if(bH[k] < bH[j])
            swap(k, j);
        else if(bH[k] > bH[j]) 
            break;
        k = j;
    }
}

private boolean max(int i, int j) {
    if(bH[i] < bH[j])
        return true;
    return false;
}

private void swap(int i, int j) {
    int temp = 0;
    temp = bH[i];
    bH[i] = bH[j];
    bH[j] = temp;
}

private void printAll() {
    for(int i=1; i < this.k; i++)
    {
        System.out.print(bH[i] + " ");
    }       
    System.out.println();
}

public static void main(String[] args) throws Exception
{
    int a[] = {6,5,7,8,2,9,8,1};
    BinaryHeap bh = new BinaryHeap(a.length);
    for(int i=0; i < a.length; i++)
    {
        bh.put(a[i]);
    }

    System.out.println("Elements in Binary Heap: ");
    bh.printAll();

    System.out.println("Deleting Minimum: ");
    bh.deleteMin();
    bh.printAll();

    System.out.println("Deleting Maximum: ");
    bh.deleteMax();
    bh.printAll();
}}

Спасибо, ~ N

Answer 5

Используйте эту функцию для достижения нужного узла:

function find_node($n)
{
$current_node = $n;
while($current_node > 1)
{
    if($current_node % 2 == 1) // if node is odd it is a right child
    {
      push($stack,"Right");
    }
    else // otherwise it is even and left child
    {
      push($stack,"Left");
    }
    $current_node = floor($current_node / 2); // set the current node to the parent
}
return $stack; // this stack now contains the path to node n
}