java - Binary Min Heap 的链表实现（操作有问题...）

Question

所以我正在尝试实现一个二进制最小堆。我了解二进制最小堆在其结构和属性方面的含义。但是，当我尝试使用指针和节点来实现它时，我碰壁了。

我使用的是Node, right/left and pointers,int element和parent pointer. 我还有一个LastNodein place 指向插入的最后一个节点。

我的争吵是当我插入一个元素时，我不知道该怎么做，就最后一个节点而言。这就是我的意思。

步骤 1.) 假设 Heap 是空的，因此您创建一个root即 x 其中 x 包含元素并且您设置root.left/right = nulland LastNode = root.left。

  X
 / \
0   0

这是我卡住的部分。我知道当您创建另一个节点来存储另一个元素时，它将位于 X 的左侧或 LastNode 指向的位置。我的问题我接下来用 LastNode 做什么，我是否将它指向 x.right ？我试图继续insert(int x)在 logN 中运行，并且 lastNode 操作将在每个级别变得更长和更广泛。

有人可以分解吗？谢谢

score 1 · Accepted Answer

Since you have to insert nodes at the bottom level, ie breadth wise , what if you maintain a record of all nodes inserted so far in a queue? When you insert a new node in the heap, find the latest position from the queue and insert the data there. Then heapify_up that node.

score 1 · Accepted Answer

好吧，您需要在堆的最后一层插入元素，然后从那里确定是否需要冒泡。所以你需要 lastNode 指针来指示不是插入的最后一个元素（它很可能是最后一个插入的元素，但它可能已经一直上升到现在的根；这根本没有帮助），而是您将在其中插入这个新元素。这有帮助吗？

（稍后编辑）：有一种更优化的方式来构建堆，但我觉得这不是你现在需要的，所以这就是为什么我假设你会使用简单的插入，每个新的都是 O(log n)元素。

score 1 · Accepted Answer

我想另一种方法是保留树中每个节点的所有子元素的计数。由于二叉堆的主要目标是完全平衡，您可以决定插入新节点或它们的键，向左或向右取决于树的哪一侧不太平衡。

我目前正在尝试使用 Java 编写 Binary Hep 代码，并且被困在同一点上。我想出了这种平衡堆的方法，并解决了在哪里插入新节点的问题。这仍然应该保持堆实现的复杂性。

将在某个时候发布代码。如果有人对此有任何问题或认为这不是正确的做法，请纠正我。

更新：这是代码（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

score 0 · Accepted Answer

我有同样的家庭作业。我找到的解决方案是逐级降低二叉树，每次根据底部节点的数量决定左转或右转。我为此做了一个递归算法。

例如，假设您想在以下树中放置一个新节点：

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

从顶部开始，您会发现底部有 2/4 个完整节点。因此，您通过正确的分支下降并发现自己位于树的顶部，并带有 root C。在这棵树的底部有 0/2 个完整节点，因此您通过左分支下降并发现自己位于叶节点，因此这是放置新元素的位置。

这是我用来计算树高度的 Java 代码，具有任何给定高度的树底部的可能节点数，以及具有 size 的树底部的完整或“已使用”节点的数量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);
}

score -1 · Accepted Answer

使用此功能到达所需节点：

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
}

java - Binary Min Heap 的链表实现（操作有问题...）

5 回答 5

Related

Reference