java 二元最小堆的链表实现（操作有问题...）

Linked list implementation of Binary Min Heap (Having trouble with manipulation...)

提问by smooth_smoothie

So i'm trying to implement a binary min heap. I understand what the binary min heap entails in terms of it's structure and it's properties. However I'm hitting a wall when I'm trying to implement it using pointers and nodes.

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

Im using a Node, which has right/left and pointers, int elementand parent pointer. I also have a LastNodein place which points to the last node inserted.

我正在使用 a Node，其中有right/left and pointers,int element和parent pointer。我也有一个LastNode指向插入的最后一个节点的位置。

My quarrel is I dont know what to do when I insert an element, in terms of the last Node. Here is what I mean.

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

Step 1.) Assume Heap is empty, so you create a rootnamely x where x contains the element and you set root.left/right = nulland LastNode = root.left.

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

  X
 / \
0   0

This is the part where I'm stuck. I know when you create another node to store another element it will go in the left of X or where LastNode points to. My questions what do I do next with LastNode, do I point it to x.right ? I'm trying to keep insert(int x)running in logN, and The lastNode manipulation will get longer and more extensive at each level.

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

Can someone break it down? Thanks

有人可以分解吗？谢谢

回答by Alex Florescu

Well you need to insert the element on the last level of the heap and then from there figure out if you need to bubble up. So you need the lastNode pointer to indicate not the last element inserted (it could very well be the last one insterted, but it might have went all the way up being now the root; that's not helpful at all), but rather the parent of where you will insert this new element. Does that help?

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

(Later edit): There is a more optimal way of building the heap, but I feel that's not what you need right now, so that's why I assumed you'll be using the simple insertion with is O(log n) for every new element.

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

回答by Hina

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.

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

回答by Naveen

I guess one more way of doing this would be to keep the count of all child elements for each node in the Tree. Since the main aim of the Binary heap is to be completely balanced, you can decide to insert the new node or they key, either towards the left or the right depending upon which side the tree is less balanced.

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

I am currently trying to write the Binary Hep code using Java and am stuck at this very same point. I have come up with this approach of balancing my Heap as well as solve the problem of where to insert the new node. This should still maintain the complexities of the Heap implementation.

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

Will post the code in sometime. If someone sees any issues with this or think that this is not the right way to do it, please do correct me.

有时间会贴出代码。如果有人看到任何问题或认为这不是正确的方法，请纠正我。

Update: Here's the code (https://gist.github.com/naveenwashere/5607516):

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

Thanks, ~N

谢谢~N

回答by kryo

I had the same homework assignment. The solution I found is to step down your binary tree level by level, each time deciding to make a left or a right turn depending on the number of nodes at the bottom. I made a recursive algorithm for this.

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

For example, say you want to place a new node in the following tree:

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

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

Starting at the top, you find that there are 2/4 full nodes at the bottom. Therefore you descend via the right branch and find yourself at the top of the tree with root C. At the bottom of this tree there are 0/2 full nodes, so you descend via the left branch and find yourself at a leaf node, so that is where you place the new element.

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

Here is the Java code I used to calculate the height of a tree, the number of possible nodes at the bottom of a tree with any given height, and the number of full or "used" nodes at the bottom of a tree with size size.

这是我用来计算树的高度的 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);
}

回答by Orhun Alp Oral

Use this function to reach desired node:

使用此函数到达所需节点：

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
}