Max-Heap实施:如何使第一个3节点始终成为最高?
因此,我一直在尝试实现最大堆。我想给予的用途是,我希望任何一次,我希望堆的前3个要素(即根和两个孩子)在整个堆中始终是最高的。
i认为堆属性可以保证这一点,但我遇到的一个实现示例并不能解决一个事实,有时,在一个层次的一个级别上,元素中存在元素的元素,其级别低于较高级别的元素。 这是我一直在使用的实现,基本上是使用我在Internet上找到的示例作为参考:
let createHeap = function(){
return {
arr:[],
size: 0,
getParent: function(i) { return Math.floor((i-1)/2) },
getLeft: function(i) { return (2*i + 1) },
getRight: function(i) { return (2*i + 2) },
insert: function(val){
let i = this.size
this.size++
this.arr[i] = val;
if(i!=0){
for(let j = this.getParent(i);j>=0;j--){
this.heapify(j)
}
}
},
heapify: function(i){
let largest = i;
let leftIndex = this.getLeft(i)
let rightIndex = this.getRight(i)
if (leftIndex < this.size && this.arr[leftIndex] > this.arr[largest])
largest = leftIndex
if (rightIndex < this.size && this.arr[rightIndex] > this.arr[largest])
largest = rightIndex;
if (largest != i) {
let temp = this.arr[largest];
this.arr[largest] = this.arr[i]
this.arr[i] = temp
this.heapify(largest);
}
}
}
}
现在,问题是,当我以此顺序插入以下值时:1,2,2,3,4,, 5
我要获得的结果是:
5
|\
4 2
|\
1 3
当您阅读代码的作用时,这很明显,但只要我必须了解堆属性的含义,但似乎并没有保留堆的属性。该代码缺少某些事情无法做我想做的事情,但是我不想实施会增加复杂性的更改,所以我想问:
- 有人知道实施是否错误还是从来没有想做我想做的事? (堆的前三个要素在整个堆中始终是最高的)
- 什么是实施此功能的最佳方法,而不会增加复杂性?
So I've been trying to implement the Max Heap. The use I want to give to it is that, at any one time, I want the first 3 elements of the heap (that is, the root and its two children) to always be the highest in the whole heap.
I thought the heap property would guarantee this, but not a single implementation example I have come across has been able to solve the fact that sometimes, there are elements in one level of the heap that are lower than an element in a higher level.
This is the implementation I've been using, basically by using examples I have found on the internet as reference:
let createHeap = function(){
return {
arr:[],
size: 0,
getParent: function(i) { return Math.floor((i-1)/2) },
getLeft: function(i) { return (2*i + 1) },
getRight: function(i) { return (2*i + 2) },
insert: function(val){
let i = this.size
this.size++
this.arr[i] = val;
if(i!=0){
for(let j = this.getParent(i);j>=0;j--){
this.heapify(j)
}
}
},
heapify: function(i){
let largest = i;
let leftIndex = this.getLeft(i)
let rightIndex = this.getRight(i)
if (leftIndex < this.size && this.arr[leftIndex] > this.arr[largest])
largest = leftIndex
if (rightIndex < this.size && this.arr[rightIndex] > this.arr[largest])
largest = rightIndex;
if (largest != i) {
let temp = this.arr[largest];
this.arr[largest] = this.arr[i]
this.arr[i] = temp
this.heapify(largest);
}
}
}
}
Now, the problem is, when I insert the following values in this order: 1, 2, 3, 4, 5
The result I get for the heap is:
5
|\
4 2
|\
1 3
This is clear when you read what the code does, but doesn't seem to conserve heap property as far as I got to understand what heap property means. The code is missing something to get to do what I want it to do, but I don't want to implement changes that would increase the complexity too badly, so I wanted to ask:
- Does anyone know if the implementation is wrong or if it was never meant to do what I want it to do? (first 3 elements of the heap are always the highest in the whole heap)
- What would be the best way of implementing this without increasing the complexity too much?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论