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

发布于 2024-10-29 02:42:46 字数 637 浏览 6 评论 0原文

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

我使用的是节点,它有右/左和指针int元素父指针。我还有一个 LastNode 指向最后插入的节点。

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

步骤 1.) 假设堆为空,因此您创建一个 root,即 x,其中 x 包含该元素,并设置 root.left/right = nullLastNode = root.left

  X
 / \
0   0

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

有人可以分解它吗? 谢谢

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 element and parent pointer. I also have a LastNode in place which points to the last node inserted.

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.

Step 1.) Assume Heap is empty, so you create a root namely x where x contains the element and you set root.left/right = null and 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.

Can someone break it down?
Thanks

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

执着的年纪 2024-11-05 02:42:46

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

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

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?

(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.

林空鹿饮溪 2024-11-05 02:42:46

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

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.

七度光 2024-11-05 02:42:46

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

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

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.

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):

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

乞讨 2024-11-05 02:42:46

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

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

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

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.

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.

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);
}
反差帅 2024-11-05 02:42:46

使用此函数到达所需的节点:

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
}

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
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文