双向更新堆（Prim 算法）
Updating Heap in both direction (Prim's Algorithm)
在Prim的算法中，推荐通过以下方式保持不变量：
When a vertice v is added to the MST:
For each edge (v,w) in the unexplored tree:
1. Delete w from the min heap.
2. Recompute the key[w] (i.e. it's value from the unexplored tree
to the explored one).
3. Add the value back to the heap.
所以，基本上这涉及从堆中删除（以及需要 O(logn) 的 heapify）然后重新插入（再次 O(logn)）
相反，如果我使用以下方法：
For each edge (v,w) in the unexplored tree:
1. Get the position of the node in the heap(array) using HashMap -> O(1)
2. Update the value in place.
3. Bubble up or bubble down accordingly. -> O(logn)
它给出了比前一个更好的常量。
有争议的部分是第三部分，我应该向上或向下冒泡。
我的实现如下：
public int heapifyAt(int index){
// Bubble up
if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
swap(index, (int)Math.floor(index/2));
index = (int)Math.floor(index/2);
}
}else{
// Bubble down
while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
//swap with left child
swap(index, index*2 + 1);
index = index*2 + 1;
}else{
//swap with right child
swap(index, index*2 + 2);
index = index*2 + 2;
}
}
}
return index;
}
我正以这种方式从堆中采摘 :
public AdjNode pluck(){
AdjNode min = heap[0];
int minNodeNumber = heap[0].nodeNumber;
AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
heap[0].edgeCost = INF; // set this to infinity, so it'll be at the bottom
// of the heap.
heapifyat(0);
visited.add(minNodeNumber);
updatevertices(minNodeNumber); // Update the adjacent vertices
return toRet;
}
并以这种方式更新采摘的顶点：
public void updatevertices(int pluckedNode){
for(AdjNode adjacentNode : g.list[pluckedNode]){
if(!visited.contains(adjacentNode.nodeNumber)){ // Skip the nodes that are already visited
int positionInHeap = map.get(adjacentNode.nodeNumber); // Retrive the position from HashMap
if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
heap[positionInHeap].edgeCost = adjacentNode.edgeCost; // Update if the cost is better
heapifyAt(positionInHeap); // Now this will go bottom or up, depending on the value
}
}
}
}
但是当我在大图上执行它时，代码失败，堆底部有小值，顶部有大值。但是 heapifyAt() API 似乎工作正常。所以我无法弄清楚是我的方法错误还是我的代码？
此外，如果我用 siftDown() 替换 heapifyAt() API，即构建堆， 它工作正常，但是调用 siftDown() 没有意义(n) 每次更新的时间，可以用对数时间处理。
简而言之：是否可以双向更新堆中的值，或者算法错误，因为这就是为什么建议先从堆中删除元素并重新插入它.
编辑：完整代码：
public class Graph1{
public static final int INF = 9999999;
public static final int NEGINF = -9999999;
static class AdjNode{
int nodeNumber;
int edgeCost;
AdjNode next;
AdjNode(int nodeNumber, int edgeCost){
this.nodeNumber = nodeNumber;
this.edgeCost = edgeCost;
}
}
static class AdjList implements Iterable<AdjNode>{
AdjNode head;
AdjList(){
}
public void add(int to, int cost){
if(head==null){
head = new AdjNode(to, cost);
}else{
AdjNode temp = head;
while(temp.next!=null){
temp = temp.next;
}
temp.next = new AdjNode(to, cost);
}
}
public Iterator<AdjNode> iterator(){
return new Iterator<AdjNode>(){
AdjNode temp = head;
public boolean hasNext(){
if(head==null){
return false;
}
return temp != null;
}
public AdjNode next(){
AdjNode ttemp = temp;
temp = temp.next;
return ttemp;
}
public void remove(){
throw new UnsupportedOperationException();
}
};
}
public void printList(){
AdjNode temp = head;
if(head==null){
System.out.println("List Empty");
return;
}
while(temp.next!=null){
System.out.print(temp.nodeNumber + "|" + temp.edgeCost + "-> ");
temp = temp.next;
}
System.out.println(temp.nodeNumber + "|" + temp.edgeCost);
}
}
static class Heap{
int size;
AdjNode[] heap;
Graph g;
int pluckSize;
Set<Integer> visited = new HashSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<>();
Heap(){
}
Heap(Graph g){
this.g = g;
this.size = g.numberOfVertices;
this.pluckSize = size - 1;
heap = new AdjNode[size];
copyElements();
constructHeap();
}
public void copyElements(){
AdjList first = g.list[0];
int k = 0;
heap[k++] = new AdjNode(0, NEGINF); //First entry
for(AdjNode nodes : first){
heap[nodes.nodeNumber] = nodes;
}
for(int i=0; i<size; i++){
if(heap[i]==null){
heap[i] = new AdjNode(i, INF);
}
}
}
public void printHashMap(){
System.out.println("Priniting HashMap");
for(int i=0; i<size; i++){
System.out.println(i + " Pos in heap :" + map.get(i));
}
line();
}
public void line(){
System.out.println("*******************************************");
}
public void printHeap(){
System.out.println("Printing Heap");
for(int i=0; i<size; i++){
System.out.println(heap[i].nodeNumber + " | " + heap[i].edgeCost);
}
line();
}
public void initializeMap(){
for(int i=0; i<size; i++){
map.put(heap[i].nodeNumber, i);
}
}
public void swap(int one, int two){
AdjNode first = heap[one];
AdjNode second = heap[two];
map.put(first.nodeNumber, two);
map.put(second.nodeNumber, one);
AdjNode temp = heap[one];
heap[one] = heap[two];
heap[two] = temp;
}
public void constructHeap(){
for(int i=size-1; i>=0; i--){
int temp = i;
while(heap[temp].edgeCost < heap[(int)Math.floor(temp/2)].edgeCost){
swap(temp, (int)Math.floor(temp/2));
temp = (int)Math.floor(temp/2);
}
}
initializeMap();
}
public void updatevertices(int pluckedNode){
for(AdjNode adjacentNode : g.list[pluckedNode]){
if(!visited.contains(adjacentNode.nodeNumber)){
int positionInHeap = map.get(adjacentNode.nodeNumber);
if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
// //System.out.println(adjacentNode.nodeNumber + " not visited, Updating vertice " + heap[positionInHeap].nodeNumber + " from " + heap[positionInHeap].edgeCost + " to " + adjacentNode.edgeCost);
// heap[positionInHeap].edgeCost = INF;
// //heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
// int heapifiedIndex = heapifyAt(positionInHeap); // This code follows my logic
// heap[heapifiedIndex].edgeCost = adjacentNode.edgeCost; // (which doesnt work)
// //heapifyAt(size - 1);
heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
//heapifyAt(positionInHeap);
constructHeap(); // When replaced by SiftDown,
} // works as charm
}
}
}
public void printSet(){
Iterator<Integer> it = visited.iterator();
System.out.print("Printing set : [");
while(it.hasNext()){
System.out.print((int)it.next() + ", ");
}
System.out.println("]");
}
public AdjNode pluck(){
AdjNode min = heap[0];
int minNodeNumber = heap[0].nodeNumber;
AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
heap[0].edgeCost = INF;
constructHeap();
visited.add(minNodeNumber);
updatevertices(minNodeNumber);
return toRet;
}
public int heapifyAt(int index){
if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
swap(index, (int)Math.floor(index/2));
index = (int)Math.floor(index/2);
}
}else{
if(index*2 + 2 < size){
while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
//swap with left child
swap(index, index*2 + 1);
index = index*2 + 1;
}else{
//swap with right child
swap(index, index*2 + 2);
index = index*2 + 2;
}
}
}
}
return index;
}
}
static class Graph{
int numberOfVertices;
AdjList[] list;
Graph(int numberOfVertices){
list = new AdjList[numberOfVertices];
for(int i=0; i<numberOfVertices; i++){
list[i] = new AdjList();
}
this.numberOfVertices = numberOfVertices;
}
public void addEdge(int from, int to, int cost){
this.list[from].add(to, cost);
this.list[to].add(from, cost);
}
public void printGraph(){
System.out.println("Printing Graph");
for(int i=0; i<numberOfVertices; i++){
System.out.print(i + " = ");
list[i].printList();
}
}
}
public static void prims(Graph graph, Heap heap){
int totalMin = INF;
int tempSize = graph.numberOfVertices;
while(tempSize>0){
AdjNode min = heap.pluck();
totalMin += min.edgeCost;
System.out.println("Added cost : " + min.edgeCost);
tempSize--;
}
System.out.println("Total min : " + totalMin);
}
public static void main(String[] args) throws Throwable {
Scanner in = new Scanner(new File("/home/mayur/Downloads/PrimsInput.txt"));
Graph graph = new Graph(in.nextInt());
in.nextInt();
while(in.hasNext()){
graph.addEdge(in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
}
Heap heap = new Heap(graph);
prims(graph, heap);
}
}
通过正确实施堆，您应该能够向上 和 向下冒泡。堆使用适用于两个方向的顺序保留一组元素，向上和向下冒泡本质上是相同的，除了你移动的方向。
关于您的实施，我相信您是正确的，但有一个看似次要的问题：索引。
如果你四处寻找堆的数组实现，你会注意到在大多数情况下根位于索引 1，而不是 0。原因是，在一个索引为 1 的数组中你保留了以下内容parent p 和 children c1 和 c2.
之间的关系
heap[i] = p
heap[2 * i] = c1
heap[2 * i + 1] = c2
在一张纸上画一个数组并看到这个关系成立是微不足道的，如果你的根在堆[1]。 root 的 children 在索引 1 处位于索引 2 和 3。索引 2 处的节点的 Children 位于索引 4 和 5，而节点的 children索引 3 位于索引 6 和 7，依此类推。
这种关系可以帮助您到达 i 处任何节点的 children 或 parent，而无需跟踪它们的位置。 （即 parent 在 floor(i/2) 而 children 在 2i 和 2i+1）
您似乎尝试过的是堆的 0 索引实现。因此，对于 parent p 和 children c1 和 c2，您必须使用下面给出的稍微不同的关系.
heap[i] = p
heap[2 * i + 1] = c1
heap[2 * i + 2] = c2
访问children时好像没问题。例如，root 的 children，索引为 0，位于索引 1 和 2。索引 1 的节点的 Children 位于索引 3 和 4，而 children索引 2 处的节点位于索引 5 和 6，依此类推。但是，访问节点的 parent 时会出现问题。如果您考虑节点 3 并取 floor(3/2)，您会得到索引 1，其中 是 1 的 parent。但是，如果您取索引处的节点4，floor(4/2) 给你索引 2，它是 not 索引 4.
节点的 parent
显然，parent 和它的 children 之间索引关系的这种适配对两个 children 都不起作用。与 1 索引堆实现不同，在访问它们的 parents 时，您不能对两个 children 进行相同的处理。所以，问题具体出在你的冒泡部分，不一定与冒泡操作有关。其实，虽然我没有测试你的代码，但是冒泡部分heapifyAt 函数似乎是正确的。（即 除了 索引，当然）
现在，您可以继续使用 0 索引堆并调整您的代码，以便每当您查找节点的 parent 时，您隐式检查它是否是 正确的 （即不是正确的，而是与左边相反的）parent 的 child，如果是，则使用 floor((i-1)/2)。检查一个节点是否是正确的 child 是微不足道的：只看它是否是偶数。 （即，当你用 2i + 2 对 children 进行索引时，它们将始终是偶数）
不过，我建议您采用不同的方法，而不是 使用堆的 1 索引数组实现。堆的数组实现的优雅之处在于，您可以相同地对待每个节点，而不必根据其索引或位置做任何不同的事情，堆的根可能是唯一可能的例外。
在Prim的算法中，推荐通过以下方式保持不变量：
When a vertice v is added to the MST:
For each edge (v,w) in the unexplored tree:
1. Delete w from the min heap.
2. Recompute the key[w] (i.e. it's value from the unexplored tree
to the explored one).
3. Add the value back to the heap.
所以，基本上这涉及从堆中删除（以及需要 O(logn) 的 heapify）然后重新插入（再次 O(logn)）
相反，如果我使用以下方法：
For each edge (v,w) in the unexplored tree:
1. Get the position of the node in the heap(array) using HashMap -> O(1)
2. Update the value in place.
3. Bubble up or bubble down accordingly. -> O(logn)
它给出了比前一个更好的常量。
有争议的部分是第三部分，我应该向上或向下冒泡。
我的实现如下：
public int heapifyAt(int index){
// Bubble up
if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
swap(index, (int)Math.floor(index/2));
index = (int)Math.floor(index/2);
}
}else{
// Bubble down
while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
//swap with left child
swap(index, index*2 + 1);
index = index*2 + 1;
}else{
//swap with right child
swap(index, index*2 + 2);
index = index*2 + 2;
}
}
}
return index;
}
我正以这种方式从堆中采摘 :
public AdjNode pluck(){
AdjNode min = heap[0];
int minNodeNumber = heap[0].nodeNumber;
AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
heap[0].edgeCost = INF; // set this to infinity, so it'll be at the bottom
// of the heap.
heapifyat(0);
visited.add(minNodeNumber);
updatevertices(minNodeNumber); // Update the adjacent vertices
return toRet;
}
并以这种方式更新采摘的顶点：
public void updatevertices(int pluckedNode){
for(AdjNode adjacentNode : g.list[pluckedNode]){
if(!visited.contains(adjacentNode.nodeNumber)){ // Skip the nodes that are already visited
int positionInHeap = map.get(adjacentNode.nodeNumber); // Retrive the position from HashMap
if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
heap[positionInHeap].edgeCost = adjacentNode.edgeCost; // Update if the cost is better
heapifyAt(positionInHeap); // Now this will go bottom or up, depending on the value
}
}
}
}
但是当我在大图上执行它时，代码失败，堆底部有小值，顶部有大值。但是 heapifyAt() API 似乎工作正常。所以我无法弄清楚是我的方法错误还是我的代码？ 此外，如果我用 siftDown() 替换 heapifyAt() API，即构建堆， 它工作正常，但是调用 siftDown() 没有意义(n) 每次更新的时间，可以用对数时间处理。
简而言之：是否可以双向更新堆中的值，或者算法错误，因为这就是为什么建议先从堆中删除元素并重新插入它.
编辑：完整代码：
public class Graph1{
public static final int INF = 9999999;
public static final int NEGINF = -9999999;
static class AdjNode{
int nodeNumber;
int edgeCost;
AdjNode next;
AdjNode(int nodeNumber, int edgeCost){
this.nodeNumber = nodeNumber;
this.edgeCost = edgeCost;
}
}
static class AdjList implements Iterable<AdjNode>{
AdjNode head;
AdjList(){
}
public void add(int to, int cost){
if(head==null){
head = new AdjNode(to, cost);
}else{
AdjNode temp = head;
while(temp.next!=null){
temp = temp.next;
}
temp.next = new AdjNode(to, cost);
}
}
public Iterator<AdjNode> iterator(){
return new Iterator<AdjNode>(){
AdjNode temp = head;
public boolean hasNext(){
if(head==null){
return false;
}
return temp != null;
}
public AdjNode next(){
AdjNode ttemp = temp;
temp = temp.next;
return ttemp;
}
public void remove(){
throw new UnsupportedOperationException();
}
};
}
public void printList(){
AdjNode temp = head;
if(head==null){
System.out.println("List Empty");
return;
}
while(temp.next!=null){
System.out.print(temp.nodeNumber + "|" + temp.edgeCost + "-> ");
temp = temp.next;
}
System.out.println(temp.nodeNumber + "|" + temp.edgeCost);
}
}
static class Heap{
int size;
AdjNode[] heap;
Graph g;
int pluckSize;
Set<Integer> visited = new HashSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<>();
Heap(){
}
Heap(Graph g){
this.g = g;
this.size = g.numberOfVertices;
this.pluckSize = size - 1;
heap = new AdjNode[size];
copyElements();
constructHeap();
}
public void copyElements(){
AdjList first = g.list[0];
int k = 0;
heap[k++] = new AdjNode(0, NEGINF); //First entry
for(AdjNode nodes : first){
heap[nodes.nodeNumber] = nodes;
}
for(int i=0; i<size; i++){
if(heap[i]==null){
heap[i] = new AdjNode(i, INF);
}
}
}
public void printHashMap(){
System.out.println("Priniting HashMap");
for(int i=0; i<size; i++){
System.out.println(i + " Pos in heap :" + map.get(i));
}
line();
}
public void line(){
System.out.println("*******************************************");
}
public void printHeap(){
System.out.println("Printing Heap");
for(int i=0; i<size; i++){
System.out.println(heap[i].nodeNumber + " | " + heap[i].edgeCost);
}
line();
}
public void initializeMap(){
for(int i=0; i<size; i++){
map.put(heap[i].nodeNumber, i);
}
}
public void swap(int one, int two){
AdjNode first = heap[one];
AdjNode second = heap[two];
map.put(first.nodeNumber, two);
map.put(second.nodeNumber, one);
AdjNode temp = heap[one];
heap[one] = heap[two];
heap[two] = temp;
}
public void constructHeap(){
for(int i=size-1; i>=0; i--){
int temp = i;
while(heap[temp].edgeCost < heap[(int)Math.floor(temp/2)].edgeCost){
swap(temp, (int)Math.floor(temp/2));
temp = (int)Math.floor(temp/2);
}
}
initializeMap();
}
public void updatevertices(int pluckedNode){
for(AdjNode adjacentNode : g.list[pluckedNode]){
if(!visited.contains(adjacentNode.nodeNumber)){
int positionInHeap = map.get(adjacentNode.nodeNumber);
if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
// //System.out.println(adjacentNode.nodeNumber + " not visited, Updating vertice " + heap[positionInHeap].nodeNumber + " from " + heap[positionInHeap].edgeCost + " to " + adjacentNode.edgeCost);
// heap[positionInHeap].edgeCost = INF;
// //heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
// int heapifiedIndex = heapifyAt(positionInHeap); // This code follows my logic
// heap[heapifiedIndex].edgeCost = adjacentNode.edgeCost; // (which doesnt work)
// //heapifyAt(size - 1);
heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
//heapifyAt(positionInHeap);
constructHeap(); // When replaced by SiftDown,
} // works as charm
}
}
}
public void printSet(){
Iterator<Integer> it = visited.iterator();
System.out.print("Printing set : [");
while(it.hasNext()){
System.out.print((int)it.next() + ", ");
}
System.out.println("]");
}
public AdjNode pluck(){
AdjNode min = heap[0];
int minNodeNumber = heap[0].nodeNumber;
AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
heap[0].edgeCost = INF;
constructHeap();
visited.add(minNodeNumber);
updatevertices(minNodeNumber);
return toRet;
}
public int heapifyAt(int index){
if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
swap(index, (int)Math.floor(index/2));
index = (int)Math.floor(index/2);
}
}else{
if(index*2 + 2 < size){
while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
//swap with left child
swap(index, index*2 + 1);
index = index*2 + 1;
}else{
//swap with right child
swap(index, index*2 + 2);
index = index*2 + 2;
}
}
}
}
return index;
}
}
static class Graph{
int numberOfVertices;
AdjList[] list;
Graph(int numberOfVertices){
list = new AdjList[numberOfVertices];
for(int i=0; i<numberOfVertices; i++){
list[i] = new AdjList();
}
this.numberOfVertices = numberOfVertices;
}
public void addEdge(int from, int to, int cost){
this.list[from].add(to, cost);
this.list[to].add(from, cost);
}
public void printGraph(){
System.out.println("Printing Graph");
for(int i=0; i<numberOfVertices; i++){
System.out.print(i + " = ");
list[i].printList();
}
}
}
public static void prims(Graph graph, Heap heap){
int totalMin = INF;
int tempSize = graph.numberOfVertices;
while(tempSize>0){
AdjNode min = heap.pluck();
totalMin += min.edgeCost;
System.out.println("Added cost : " + min.edgeCost);
tempSize--;
}
System.out.println("Total min : " + totalMin);
}
public static void main(String[] args) throws Throwable {
Scanner in = new Scanner(new File("/home/mayur/Downloads/PrimsInput.txt"));
Graph graph = new Graph(in.nextInt());
in.nextInt();
while(in.hasNext()){
graph.addEdge(in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
}
Heap heap = new Heap(graph);
prims(graph, heap);
}
}
通过正确实施堆，您应该能够向上 和 向下冒泡。堆使用适用于两个方向的顺序保留一组元素，向上和向下冒泡本质上是相同的，除了你移动的方向。
关于您的实施，我相信您是正确的，但有一个看似次要的问题：索引。
如果你四处寻找堆的数组实现，你会注意到在大多数情况下根位于索引 1，而不是 0。原因是，在一个索引为 1 的数组中你保留了以下内容parent p 和 children c1 和 c2.
之间的关系heap[i] = p heap[2 * i] = c1 heap[2 * i + 1] = c2
在一张纸上画一个数组并看到这个关系成立是微不足道的，如果你的根在堆[1]。 root 的 children 在索引 1 处位于索引 2 和 3。索引 2 处的节点的 Children 位于索引 4 和 5，而节点的 children索引 3 位于索引 6 和 7，依此类推。
这种关系可以帮助您到达 i 处任何节点的 children 或 parent，而无需跟踪它们的位置。 （即 parent 在 floor(i/2) 而 children 在 2i 和 2i+1）
您似乎尝试过的是堆的 0 索引实现。因此，对于 parent p 和 children c1 和 c2，您必须使用下面给出的稍微不同的关系.
heap[i] = p heap[2 * i + 1] = c1 heap[2 * i + 2] = c2
访问children时好像没问题。例如，root 的 children，索引为 0，位于索引 1 和 2。索引 1 的节点的 Children 位于索引 3 和 4，而 children索引 2 处的节点位于索引 5 和 6，依此类推。但是，访问节点的 parent 时会出现问题。如果您考虑节点 3 并取 floor(3/2)，您会得到索引 1，其中 是 1 的 parent。但是，如果您取索引处的节点4，floor(4/2) 给你索引 2，它是 not 索引 4.
节点的 parent显然，parent 和它的 children 之间索引关系的这种适配对两个 children 都不起作用。与 1 索引堆实现不同，在访问它们的 parents 时，您不能对两个 children 进行相同的处理。所以，问题具体出在你的冒泡部分，不一定与冒泡操作有关。其实，虽然我没有测试你的代码，但是冒泡部分heapifyAt 函数似乎是正确的。（即 除了 索引，当然）
现在，您可以继续使用 0 索引堆并调整您的代码，以便每当您查找节点的 parent 时，您隐式检查它是否是 正确的 （即不是正确的，而是与左边相反的）parent 的 child，如果是，则使用 floor((i-1)/2)。检查一个节点是否是正确的 child 是微不足道的：只看它是否是偶数。 （即，当你用 2i + 2 对 children 进行索引时，它们将始终是偶数）
不过，我建议您采用不同的方法，而不是 使用堆的 1 索引数组实现。堆的数组实现的优雅之处在于，您可以相同地对待每个节点，而不必根据其索引或位置做任何不同的事情，堆的根可能是唯一可能的例外。