MinHeap删除理解
MinHeap Delete Understanding
我很难理解教授给我的关于堆的其中一个问题的解决方案。
Give pseudocode for the routine Min-Heap-Delete(A, k). Assume that key k is at location l
of the heap and that 1 ≤ l ≤ n.
我的解决办法是
Exchange A[k] with A[A.size() - 1]
A.size() = A.size() - 1
Min-heapify(A,k)
不过，我的解法和第一部分教授的解法有些不同。
Exchange A[k] with A[A.heap_size()]
A.heap_size() = A.heap_size() - 1
最小堆化(A,k)
为什么我们要使用 A.size() 而不是 A.size() - 1？ A.size() 不会过度索引表示堆的数组，因为堆从索引 1 开始吗？
在这种情况下，A.size() 会给我们 10。但是，A[10] 不存在并且会导致错误。所以，为什么不是A[10-1]获取堆树的最后一个节点呢？
因为教授使用从 1 开始的计数而不是从 0 开始的计数。注意 1 ≤ l ≤ n 条件。你可能错过了索引是 A.heap_size - 堆大小而不是数组大小，所以最后一个元素将被称为 A[9]
对于堆来说，这是比较常见的做法，也很方便，因为child/parent索引关系看起来很简单：
childs = parent * 2 and parent * 2 + 1
parent = child / 2
请注意，图片中的数组实际上是基于 zeo 的，具有未使用的零条目
我很难理解教授给我的关于堆的其中一个问题的解决方案。
Give pseudocode for the routine Min-Heap-Delete(A, k). Assume that key k is at location l of the heap and that 1 ≤ l ≤ n.
我的解决办法是
Exchange A[k] with A[A.size() - 1]
A.size() = A.size() - 1
Min-heapify(A,k)
不过，我的解法和第一部分教授的解法有些不同。
Exchange A[k] with A[A.heap_size()]
A.heap_size() = A.heap_size() - 1
最小堆化(A,k)
为什么我们要使用 A.size() 而不是 A.size() - 1？ A.size() 不会过度索引表示堆的数组，因为堆从索引 1 开始吗？
在这种情况下，A.size() 会给我们 10。但是，A[10] 不存在并且会导致错误。所以，为什么不是A[10-1]获取堆树的最后一个节点呢？
因为教授使用从 1 开始的计数而不是从 0 开始的计数。注意 1 ≤ l ≤ n 条件。你可能错过了索引是 A.heap_size - 堆大小而不是数组大小，所以最后一个元素将被称为 A[9]
对于堆来说，这是比较常见的做法，也很方便，因为child/parent索引关系看起来很简单：
childs = parent * 2 and parent * 2 + 1
parent = child / 2
请注意，图片中的数组实际上是基于 zeo 的，具有未使用的零条目