链表实现二进制最小堆（具有手法麻烦...） [英] Linked list implementation of Binary Min Heap (Having trouble with manipulation...)
问题描述
所以我想实现二进制数分堆。我明白二进制最小堆在它的结构方面和嗣继承它的属性。不过我打墙的时候我试图使用指针和节点来实现它。
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.
即时通讯使用节点，其中有左/右和指针， INT元素和父指针。我也有一个 LastNode 到位指向插入的最后一个节点。
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.
步骤1）假设堆是空的，所以你创建一个根即其中x包含元素，将 root.left /右= NULL 和 LastNode = root.left 。
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
这就是我坚持的部分。我知道，当你创建另一个节点存储其他元素，它将在X或哪里LastNode点的左边去了。我的问题是什么我LastNode接下来做，做我点它x.right？我试图让插入（INT X） logN个中运行，而该lastNode操作会在每个层次更长和更广泛的。
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
推荐答案
既然你已经在底层插入节点，即广度明智的，如果你有什么保持在队列中至今插入所有节点的记录？当你在堆中插入一个新节点，找到队列中的最新位置和插入数据在那里。然后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.
这篇关于链表实现二进制最小堆（具有手法麻烦...）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
