Max-Heap实施:如何使第一个3节点始终成为最高?

发布于 2025-01-22 14:58:23 字数 1542 浏览 0 评论 0原文

因此,我一直在尝试实现最大堆。我想给予的用途是,我希望任何一次,我希望堆的前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

当您阅读代码的作用时,这很明显,但只要我必须了解堆属性的含义,但似乎并没有保留堆的属性。该代码缺少某些事情无法做我想做的事情,但是我不想实施会增加复杂性的更改,所以我想问:

  1. 有人知道实施是否错误还是从来没有想做我想做的事? (堆的前三个要素在整个堆中始终是最高的)
  2. 什么是实施此功能的最佳方法,而不会增加复杂性?

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:

  1. 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)
  2. What would be the best way of implementing this without increasing the complexity too much?

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

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

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文