我想另一种方法是保留树中每个节点的所有子元素的计数。由于二叉堆的主要目标是完全平衡,您可以决定插入新节点或它们的键,向左或向右取决于树的哪一侧不太平衡。
我目前正在尝试使用 Java 编写 Binary Hep 代码,并且被困在同一点上。我想出了这种平衡堆的方法,并解决了在哪里插入新节点的问题。这仍然应该保持堆实现的复杂性。
将在某个时候发布代码。如果有人对此有任何问题或认为这不是正确的做法,请纠正我。
更新:这是代码(https://gist.github.com/naveenwashere/5607516):
public class BinaryHeap {
//Later you can implement a resizable array logic.
int[] bH;
public BinaryHeap(int N)
{
bH = new int[N + 1];
}
//Index of the root
int k = 1;
//The APIs
public void put(int key)
{
//Place the element at the end of the array
bH[this.k] = key;
if(bH[this.k] > bH[this.k/2])
{
//since the elements in an array implementation of the binary heap is put at the end of the array,
//we must always check if the property of the tree holds true or not.
swim(this.k);
}
this.k++;
}
public void deleteMax()
{
//Replace the element in the root with the element at the end of the array
bH[1] = bH[k];
//Restore the order of the tree
sink(1);
this.k--;
}
public void deleteMin()
{
bH[this.k - 1] = 0;
this.k--;
}
public void swim(int k)
{
while((k != 1) && (bH[k] > bH[k/2]))
{
swap(k, k/2);
k = k/2;
}
}
public void sink(int k)
{
while(2*k <= this.k)
{
int j = 2*k;
if(max(j, j+1)) j++;
if(bH[k] < bH[j])
swap(k, j);
else if(bH[k] > bH[j])
break;
k = j;
}
}
private boolean max(int i, int j) {
if(bH[i] < bH[j])
return true;
return false;
}
private void swap(int i, int j) {
int temp = 0;
temp = bH[i];
bH[i] = bH[j];
bH[j] = temp;
}
private void printAll() {
for(int i=1; i < this.k; i++)
{
System.out.print(bH[i] + " ");
}
System.out.println();
}
public static void main(String[] args) throws Exception
{
int a[] = {6,5,7,8,2,9,8,1};
BinaryHeap bh = new BinaryHeap(a.length);
for(int i=0; i < a.length; i++)
{
bh.put(a[i]);
}
System.out.println("Elements in Binary Heap: ");
bh.printAll();
System.out.println("Deleting Minimum: ");
bh.deleteMin();
bh.printAll();
System.out.println("Deleting Maximum: ");
bh.deleteMax();
bh.printAll();
}}
谢谢,~N