这个问题之前在 Stack Exchange 上被问过，但没有得到答案。
之前的问题链接： 二叉树结构实现二叉堆
如何在二叉树中实现堆。要实现堆，需要知道最后一个已填充节点和第一个未占用节点。这可以通过树的层序遍历来完成，但是如果这样做，则找到第一个未占用节点的时间复杂度将为 O(n)。所以，如何在二叉树中以 O(logn) 的时间复杂度实现堆呢？
谢谢 Shekhar
使用二叉树实现堆
22
- user2200660
4
1已经有答案了。给出的答案有什么问题吗？ - nanofarad
1答案没有提到如何找到第一个未被占用的叶子节点，它只是提到我们需要将新元素添加到第一个未被占用的叶子节点。据我所知，您需要按层遍历树来查找下一个未被占用的叶子节点，这将需要O(n)的时间复杂度。 - user2200660
据我所见，你基本上是通过存储来跟踪它。 - nanofarad
是的，我试过编写代码。问题在于，如果你没有保留一个指向父节点的指针，那么跟踪下一个未被占用的叶子节点就会成为一个问题。我们可以维护一个变量来存储这个信息，但计算需要 O(n) 的时间。假设我们在第四级（根为0），并且我们有从左边开始的4个元素在第四级中。现在，要获取下一个未被占用的叶子节点，我们需要获取第二级的兄弟节点，即进入第一级父节点。这需要 O(n) 的时间，因为我们正在以某种方式进行级别排序。 - user2200660
8个回答
42
为了使用二叉树实现具有O(log n)时间复杂度的堆，您需要将节点总数作为实例变量存储。
假设我们有一个拥有10个节点的堆。
如果我们要添加一个节点...
我们增加一个节点的总数。现在我们有11个节点总数。我们将新的节点总数(11)转换为它的二进制表示: 1011。
通过节点总数的二进制表示(1011)，我们去掉第一个数字。之后，我们使用011来导航穿过树到下一个插入节点的位置。0意味着向左走，1意味着向右走。因此，使用011，我们将向左，向右和向右走...这将把我们带到下一个插入位置。
我们每层检查一个节点，使时间复杂度为O(log n)。
假设我们有一个拥有10个节点的堆。
如果我们要添加一个节点...
我们增加一个节点的总数。现在我们有11个节点总数。我们将新的节点总数(11)转换为它的二进制表示: 1011。
通过节点总数的二进制表示(1011)，我们去掉第一个数字。之后，我们使用011来导航穿过树到下一个插入节点的位置。0意味着向左走，1意味着向右走。因此，使用011，我们将向左，向右和向右走...这将把我们带到下一个插入位置。
我们每层检查一个节点，使时间复杂度为O(log n)。
- Solace
3
7很不错。如果无法获取数字的二进制表示，您仍然可以（从根开始）确定向左还是向右。您知道树有多少级别：级别= floor( log(11)/log(2) ) = 3；您知道此级别中最左侧元素的偏移量：offset = 11 - ( 2^level - 1 );以及此级别上最多可能有多少节点：max = 2^3 = 8；如果偏移小于max的一半，则在左子树中，如果大于一半，则转到右边。随着向下移动，更新级别和偏移量即可完成！ - Bartel
2@Bartel +1，这也很不错！你们两个是从 https://www.cpp.edu/~ftang/courses/CS241/notes/Building_Heaps_With_Pointers.pdf 学到的吗？只是好奇。 - xlm
1@Bartel 另一个快速的方法是，
步骤1：如果索引是奇数-它是右子节点。
在这种情况下，11是右子节点。
步骤2：找到父索引= floor(index/2)。
在这种情况下，floor(11/2) = 5。
步骤3：重复直到获得树的根1。
在这种情况下，5 - 右子节点，
floor(5/2) = 2，
2 - 左子节点，
2/2 = 1 - 根。
所以我们得到了根、左、右、右。
1......2.....5.......11 - milanchandna
6
你不会将堆实现在二叉树中，因为堆是一个二叉树。堆维护以下顺序属性 - 给定节点V，其父节点大于或等于V。此外，堆是完整的二叉树。我在大学修过ADS课程，所以稍后我会在答案中提供我的Java堆实现。只列出您获得的主要方法复杂度：
- size() O(1)
- isEmpty() O(1)
- insert() O(logn)
- removeMin() O(logn)
- min() O(1)
这是我的Heap.java文件:
public class Heap<E extends Comparable<E>> {
private Object S[];
private int last;
private int capacity;
public Heap() {
S = new Object[11];
last = 0;
capacity = 7;
}
public Heap(int cap) {
S = new Object[cap + 1];
last = 0;
capacity = cap;
}
public int size() {
return last;
}
//
// returns the number of elements in the heap
//
public boolean isEmpty() {
return size() == 0;
}
//
// is the heap empty?
//
public E min() throws HeapException {
if (isEmpty())
throw new HeapException("The heap is empty.");
else
return (E) S[1];
}
//
// returns element with smallest key, without removal
//
private int compare(Object x, Object y) {
return ((E) x).compareTo((E) y);
}
public void insert(E e) throws HeapException {
if (size() == capacity)
throw new HeapException("Heap overflow.");
else{
last++;
S[last] = e;
upHeapBubble();
}
}
// inserts e into the heap
// throws exception if heap overflow
//
public E removeMin() throws HeapException {
if (isEmpty())
throw new HeapException("Heap is empty.");
else {
E min = min();
S[1] = S[last];
last--;
downHeapBubble();
return min;
}
}
//
// removes and returns smallest element of the heap
// throws exception is heap is empty
//
/**
* downHeapBubble() method is used after the removeMin() method to reorder the elements
* in order to preserve the Heap properties
*/
private void downHeapBubble(){
int index = 1;
while (true){
int child = index*2;
if (child > size())
break;
if (child + 1 <= size()){
//if there are two children -> take the smalles or
//if they are equal take the left one
child = findMin(child, child + 1);
}
if (compare(S[index],S[child]) <= 0 )
break;
swap(index,child);
index = child;
}
}
/**
* upHeapBubble() method is used after the insert(E e) method to reorder the elements
* in order to preserve the Heap properties
*/
private void upHeapBubble(){
int index = size();
while (index > 1){
int parent = index / 2;
if (compare(S[index], S[parent]) >= 0)
//break if the parent is greater or equal to the current element
break;
swap(index,parent);
index = parent;
}
}
/**
* Swaps two integers i and j
* @param i
* @param j
*/
private void swap(int i, int j) {
Object temp = S[i];
S[i] = S[j];
S[j] = temp;
}
/**
* the method is used in the downHeapBubble() method
* @param leftChild
* @param rightChild
* @return min of left and right child, if they are equal return the left
*/
private int findMin(int leftChild, int rightChild) {
if (compare(S[leftChild], S[rightChild]) <= 0)
return leftChild;
else
return rightChild;
}
public String toString() {
String s = "[";
for (int i = 1; i <= size(); i++) {
s += S[i];
if (i != last)
s += ",";
}
return s + "]";
}
//
// outputs the entries in S in the order S[1] to S[last]
// in same style as used in ArrayQueue
//
}
HeapException.java:
public class HeapException extends RuntimeException {
public HeapException(){};
public HeapException(String msg){super(msg);}
}
有趣的部分是
downHeapBubble()和upHeapBubble()方法，它们使性能达到O(logn)。我很快会添加关于它们的好的解释。在堆中插入新节点时，使用
upHeapBubble()方法。因此，当您插入最后一个位置时，需要调用upHeapBubble()方法，如下所示：last++;
S[last] = e;
upHeapBubble();
然后将最后一个元素与其父元素进行比较，如果父元素更大，则交换：这将最多执行logn次，其中n是节点数。因此，这里就有了logn的性能。
对于删除部分-您只能删除最小值-最高节点。因此，当您将其删除时，必须将其与最后一个节点交换-但然后您必须维护堆属性并执行downHeapBubble()。如果节点大于其子节点，请与最小的子节点交换，依此类推，直到没有子节点或没有更小的子节点为止。这可以最多执行logn次，因此这里就有了logn的性能。您可以通过查看二叉树图片here来自行解释为什么可以最多执行此操作logn次。
- Anton Belev
5
Anton，我知道使用数组实现堆的方法。我对树的实现很感兴趣。顺便说一下，谢谢你的回答。 - user2200660
我来为@Anton Belev辩护。S是我所谓的基于数组的二叉树实现。每个节点（数组元素）都有一个左子节点和右子节点，这些节点通过公式而不是指针找到，但我认为这并不能定义二叉树。即使我为另一种情况提出了建议，我认为OP应该更明确地表达。 - Mario Rossi
1为什么默认情况下要保留一个长度为11的数组？ - Nick Louloudakis
当您不想使用连续的内存空间来存储优先级堆时，就会使用基于指针的实现。 - Yossarian42
因为它是基于数组的实现，而不是二叉树的实现，这在问题中是必需的，所以被点踩了。 - C.W.
5
使用树来实现堆
我自己回答一个关于堆的问题，它需要O(log n)时间复杂度，但限制条件是要保留父节点指针。如果我们不保留父节点指针，那么需要大约O(n)时间复杂度。我发布了这个问题是为了寻求O(log n)的解决方案。
以下是计算下一个未被占用叶子节点的步骤（我们拥有父节点的指针）：
x = last inserted node. We save this after every insertion.
y = tmp node
z = next unoccupied node (next insertion)
if x is left child
z = x -> parent -> rightchild (problem solved.. that was easy)
else if x is right child
go to x's parent, until parent becomes left child. Let this node be y
(subtree rooted at y's sibling will contain the next unoccupied node)
z = y -> parent -> right -> go left until null
这是O(log n)的算法，但需要指向父节点的指针。
如果用O(n)的算法，只需按层遍历树，我们就可以得到下一个未被占用的节点的位置。
我的问题是：如何在不使用父指针的情况下O(log n)定位下一个未被占用的节点。
谢谢。
- user2200660
1
对于格式问题我感到抱歉。我使用了Ctrl+K进行格式化，结果变成了这样。 - user2200660
2
假设您想使用一个链接二叉树，没有指向父节点的指针，那么我能想到的唯一解决方案是在每个节点中保持子节点数量的计数器。
availableLeaf(node) {
if( node.left is Empty || node.right is Empty )
return node ;
else
if( node.left.count < node.right.count )
return availableLeaf(node.left)
else
return availableLeaf(node.right)
}
这种策略还可以平衡每个子树两侧节点的数量，对性能有益（尽管极其微小）。
这是O(log n)级别的。在插入时跟踪计数需要一直回到根节点，但这不会改变此操作的O(log n)级别特性。删除也是相似的情况。
其他操作都与通常的操作方式相同，并保持其性能特征。
你需要详细信息还是想自己解决？
如果您想使用仅具有左右指针而没有其他信息的链式二叉树，则建议您发起至少100,000分的悬赏。我并不是说这是不可能的（因为我没有数学证明），但我知道这已经有好几十年了。
- Mario Rossi
0
import java.util.ArrayList;
import java.util.List;
/**
* @author Harish R
*/
public class HeapPractise<T extends Comparable<T>> {
private List<T> heapList;
public List<T> getHeapList() {
return heapList;
}
public void setHeapList(List<T> heapList) {
this.heapList = heapList;
}
private int heapSize;
public HeapPractise() {
this.heapList = new ArrayList<>();
this.heapSize = heapList.size();
}
public void insert(T item) {
if (heapList.size() == 0) {
heapList.add(item);
} else {
siftUp(item);
}
}
private void siftUp(T item) {
heapList.add(item);
heapSize = heapList.size();
int currentIndex = heapSize - 1;
while (currentIndex > 0) {
int parentIndex = (int) Math.floor((currentIndex - 1) / 2);
T parentItem = heapList.get(parentIndex);
if (parentItem != null) {
if (item.compareTo(parentItem) > 0) {
heapList.set(parentIndex, item);
heapList.set(currentIndex, parentItem);
currentIndex = parentIndex;
continue;
}
}
break;
}
}
public T delete() {
if (heapList.size() == 0) {
return null;
}
if (heapList.size() == 1) {
T item = heapList.get(0);
heapList.remove(0);
return item;
}
return siftDown();
}
private T siftDown() {
T item = heapList.get(0);
T lastItem = heapList.get(heapList.size() - 1);
heapList.remove(heapList.size() - 1);
heapList.set(0, lastItem);
heapSize = heapList.size();
int currentIndex = 0;
while (currentIndex < heapSize) {
int leftIndex = (2 * currentIndex) + 1;
int rightIndex = (2 * currentIndex) + 2;
T leftItem = null;
T rightItem = null;
int currentLargestItemIndex = -1;
if (leftIndex <= heapSize - 1) {
leftItem = heapList.get(leftIndex);
}
if (rightIndex <= heapSize - 1) {
rightItem = heapList.get(rightIndex);
}
T currentLargestItem = null;
if (leftItem != null && rightItem != null) {
if (leftItem.compareTo(rightItem) >= 0) {
currentLargestItem = leftItem;
currentLargestItemIndex = leftIndex;
} else {
currentLargestItem = rightItem;
currentLargestItemIndex = rightIndex;
}
} else if (leftItem != null && rightItem == null) {
currentLargestItem = leftItem;
currentLargestItemIndex = leftIndex;
}
if (currentLargestItem != null) {
if (lastItem.compareTo(currentLargestItem) >= 0) {
break;
} else {
heapList.set(currentLargestItemIndex, lastItem);
heapList.set(currentIndex, currentLargestItem);
currentIndex = currentLargestItemIndex;
continue;
}
} else {
break;
}
}
return item;
}
public static void main(String[] args) {
HeapPractise<Integer> heap = new HeapPractise<>();
for (int i = 0; i < 32; i++) {
heap.insert(i);
}
System.out.println(heap.getHeapList());
List<Node<Integer>> nodeArray = new ArrayList<>(heap.getHeapList()
.size());
for (int i = 0; i < heap.getHeapList().size(); i++) {
Integer heapElement = heap.getHeapList().get(i);
Node<Integer> node = new Node<Integer>(heapElement);
nodeArray.add(node);
}
for (int i = 0; i < nodeArray.size(); i++) {
int leftNodeIndex = (2 * i) + 1;
int rightNodeIndex = (2 * i) + 2;
Node<Integer> node = nodeArray.get(i);
if (leftNodeIndex <= heap.getHeapList().size() - 1) {
Node<Integer> leftNode = nodeArray.get(leftNodeIndex);
node.left = leftNode;
}
if (rightNodeIndex <= heap.getHeapList().size() - 1) {
Node<Integer> rightNode = nodeArray.get(rightNodeIndex);
node.right = rightNode;
}
}
BTreePrinter.printNode(nodeArray.get(0));
System.out.println(heap.delete());
nodeArray = new ArrayList<>(heap.getHeapList().size());
for (int i = 0; i < heap.getHeapList().size(); i++) {
Integer heapElement = heap.getHeapList().get(i);
Node<Integer> node = new Node<Integer>(heapElement);
nodeArray.add(node);
}
for (int i = 0; i < nodeArray.size(); i++) {
int leftNodeIndex = (2 * i) + 1;
int rightNodeIndex = (2 * i) + 2;
Node<Integer> node = nodeArray.get(i);
if (leftNodeIndex <= heap.getHeapList().size() - 1) {
Node<Integer> leftNode = nodeArray.get(leftNodeIndex);
node.left = leftNode;
}
if (rightNodeIndex <= heap.getHeapList().size() - 1) {
Node<Integer> rightNode = nodeArray.get(rightNodeIndex);
node.right = rightNode;
}
}
BTreePrinter.printNode(nodeArray.get(0));
}
}
public class Node<T extends Comparable<?>> {
Node<T> left, right;
T data;
public Node(T data) {
this.data = data;
}
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class BTreePrinter {
public static <T extends Comparable<?>> void printNode(Node<T> root) {
int maxLevel = BTreePrinter.maxLevel(root);
printNodeInternal(Collections.singletonList(root), 1, maxLevel);
}
private static <T extends Comparable<?>> void printNodeInternal(
List<Node<T>> nodes, int level, int maxLevel) {
if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
return;
int floor = maxLevel - level;
int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
int firstSpaces = (int) Math.pow(2, (floor)) - 1;
int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;
BTreePrinter.printWhitespaces(firstSpaces);
List<Node<T>> newNodes = new ArrayList<Node<T>>();
for (Node<T> node : nodes) {
if (node != null) {
String nodeData = String.valueOf(node.data);
if (nodeData != null) {
if (nodeData.length() == 1) {
nodeData = "0" + nodeData;
}
}
System.out.print(nodeData);
newNodes.add(node.left);
newNodes.add(node.right);
} else {
newNodes.add(null);
newNodes.add(null);
System.out.print(" ");
}
BTreePrinter.printWhitespaces(betweenSpaces);
}
System.out.println("");
for (int i = 1; i <= endgeLines; i++) {
for (int j = 0; j < nodes.size(); j++) {
BTreePrinter.printWhitespaces(firstSpaces - i);
if (nodes.get(j) == null) {
BTreePrinter.printWhitespaces(endgeLines + endgeLines + i
+ 1);
continue;
}
if (nodes.get(j).left != null)
System.out.print("//");
else
BTreePrinter.printWhitespaces(1);
BTreePrinter.printWhitespaces(i + i - 1);
if (nodes.get(j).right != null)
System.out.print("\\\\");
else
BTreePrinter.printWhitespaces(1);
BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
}
System.out.println("");
}
printNodeInternal(newNodes, level + 1, maxLevel);
}
private static void printWhitespaces(int count) {
for (int i = 0; i < 2 * count; i++)
System.out.print(" ");
}
private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
if (node == null)
return 0;
return Math.max(BTreePrinter.maxLevel(node.left),
BTreePrinter.maxLevel(node.right)) + 1;
}
private static <T> boolean isAllElementsNull(List<T> list) {
for (Object object : list) {
if (object != null)
return false;
}
return true;
}
}
请注意，BTreePrinter是我很久以前从Stackoverflow某处获取的代码，并进行了修改以与两位数一起使用。如果我们转移到三位数，它将会出错，仅用于简单理解堆结构的外观。针对三位数的修复方法是将所有内容保持为3的倍数。同时，要感谢Sesh Venugopal在Youtube上提供的关于堆数据结构的精彩教程。
- Harish
0
我的堆实现
public class Heap <T extends Comparable<T>> {
private T[] arr;
private int size;
public Heap(T[] baseArr) {
this.arr = baseArr;
size = arr.length - 1;
}
public void minHeapify(int i, int n) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int smallest = i;
if (l <= n && arr[l].compareTo(arr[smallest]) < 0) {
smallest = l;
}
if (r <= n && arr[r].compareTo(arr[smallest]) < 0) {
smallest = r;
}
if (smallest != i) {
T temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
minHeapify(smallest, n);
}
}
public void buildMinHeap() {
for (int i = size / 2; i >= 0; i--) {
minHeapify(i, size);
}
}
public void heapSortAscending() {
buildMinHeap();
int n = size;
for (int i = n; i >= 1; i--) {
T temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
n--;
minHeapify(0, n);
}
}
}
- Puneet Jaiswal
-1
二叉树可以用数组表示：
import java.util.Arrays;
public class MyHeap {
private Object[] heap;
private int capacity;
private int size;
public MyHeap() {
capacity = 8;
heap = new Object[capacity];
size = 0;
}
private void increaseCapacity() {
capacity *= 2;
heap = Arrays.copyOf(heap, capacity);
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public Object top() {
return size > 0 ? heap[0] : null;
}
@SuppressWarnings("unchecked")
public Object remove() {
if (size == 0) {
return null;
}
size--;
Object res = heap[0];
Object te = heap[size];
int curr = 0, son = 1;
while (son < size) {
if (son + 1 < size
&& ((Comparable<Object>) heap[son + 1])
.compareTo(heap[son]) < 0) {
son++;
}
if (((Comparable<Object>) te).compareTo(heap[son]) <= 0) {
break;
}
heap[curr] = heap[son];
curr = son;
son = 2 * curr + 1;
}
heap[curr] = te;
return res;
}
@SuppressWarnings("unchecked")
public void insert(Object e) {
if (size == capacity) { // auto scaling
increaseCapacity();
}
int curr = size;
int parent;
heap[size] = e;
size++;
while (curr > 0) {
parent = (curr - 1) / 2;
if (((Comparable<Object>) heap[parent]).compareTo(e) <= 0) {
break;
}
heap[curr] = heap[parent];
curr = parent;
}
heap[curr] = e;
}
}
使用方法：
MyHeap heap = new MyHeap(); // it is a min heap
heap.insert(18);
heap.insert(26);
heap.insert(35);
System.out.println("size is " + heap.getSize() + ", top is " + heap.top());
heap.insert(36);
heap.insert(30);
heap.insert(10);
while(!heap.isEmpty()) {
System.out.println(heap.remove());
}
- coderz
-2
这里是 - 使用二叉树实现堆的代码
public class PriorityQ<K extends Comparable<K>> {
private class TreeNode<T extends Comparable<T>> {
T val;
TreeNode<T> left, right, parent;
public String toString() {
return this.val.toString();
}
TreeNode(T v) {
this.val = v;
left = null;
right = null;
}
public TreeNode<T> insert(T val, int position) {
TreeNode<T> parent = findNode(position/2);
TreeNode<T> node = new TreeNode<T>(val);
if(position % 2 == 0) {
parent.left = node;
} else {
parent.right = node;
}
node.parent = parent;
heapify(node);
return node;
}
private void heapify(TreeNode<T> node) {
while(node.parent != null && (node.parent.val.compareTo(node.val) < 0)) {
T temp = node.val;
node.val = node.parent.val;
node.parent.val = temp;
node = node.parent;
}
}
private TreeNode<T> findNode(int pos) {
TreeNode<T> node = this;
int reversed = 1;
while(pos > 0) {
reversed <<= 1;
reversed |= (pos&1);
pos >>= 1;
}
reversed >>= 1;
while(reversed > 1) {
if((reversed & 1) == 0) {
node = node.left;
} else {
node = node.right;
}
reversed >>= 1;
}
return node;
}
public TreeNode<T> remove(int pos) {
if(pos <= 1) {
return null;
}
TreeNode<T> last = findNode(pos);
if(last.parent.right == last) {
last.parent.right = null;
} else {
last.parent.left = null;
}
this.val = last.val;
bubbleDown();
return null;
}
public void bubbleDown() {
TreeNode<T> node = this;
do {
TreeNode<T> left = node.left;
TreeNode<T> right = node.right;
if(left != null && right != null) {
T max = left.val.compareTo(right.val) > 0 ? left.val : right.val;
if(max.compareTo(node.val) > 0) {
if(left.val.equals(max)) {
left.val = node.val;
node.val = max;
node = left;
} else {
right.val = node.val;
node.val = max;
node = right;
}
} else {
break;
}
} else if(left != null) {
T max = left.val;
if(left.val.compareTo(node.val) > 0) {
left.val = node.val;
node.val = max;
node = left;
} else {
break;
}
} else {
break;
}
} while(true);
}
}
private TreeNode<K> root;
private int position;
PriorityQ(){
this.position = 1;
}
public void insert(K val) {
if(val == null) {
return;
}
if(root == null) {
this.position = 1;
root = new TreeNode<K>(val);
this.position++;
return ;
}
root.insert(val, position);
position++;
}
public K remove() {
if(root == null) {
return null;
}
K val = root.val;
root.remove(this.position-1);
this.position--;
if(position == 1) {
root = null;
}
return val;
}
public static void main(String[] args) {
PriorityQ<Integer> q = new PriorityQ<>();
System.out.println(q.remove());
q.insert(1);
q.insert(11);
q.insert(111);
q.insert(1111);
q.remove();
q.remove();
q.remove();
q.remove();
q.insert(2);
q.insert(4);
}
}
- AKHILESH KUMAR
1
1请在您的代码中添加一些注释以使其更易于理解。同时，请解释您的解决方案与其他解决方案的不同/优势。 - user10992464
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接