二叉最小堆的链表实现（操作遇到麻烦......）

Question

所以我正在尝试实现一个二进制最小堆。我了解二进制最小堆在结构和属性方面的含义。然而，当我尝试使用指针和节点来实现它时，我遇到了困难。

我使用的是节点，它有右/左和指针、int元素和父指针。我还有一个 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

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

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

Answer 2

由于您必须在底层插入节点，即广度方面，如果您维护队列中到目前为止插入的所有节点的记录怎么办？当你在堆中插入一个新节点时，从队列中找到最新的位置并将数据插入到那里。然后 heapify_up 该节点。

Answer 3

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

我目前正在尝试使用 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

Answer 4

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

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

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

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

下面是我用来计算树的高度、任何给定高度的树底部可能的节点数以及大小 < 的树底部的完整或“已使用”节点数的 Java 代码代码>大小。

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 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
}