这个问题以前在 Stack Exchange 中被问过，但没有得到回答。
链接到之前提出的问题： 通过二叉树结构实现的二叉堆
如何在二叉树中实现堆。要实现堆，重要的是要知道最后填充的节点和第一个未占用的节点。这可以在树的级别排序中完成，但是时间复杂度将是 O(n)，只是为了找到第一个未占用的节点。那么，如何在 O(logn) 的二叉树中实现堆？
谢谢谢卡尔
问问题
45164 次
8 回答
40
要实现具有 O(log n) 时间复杂度的二叉树堆，您需要将节点总数存储为实例变量。
假设我们有一个总共 10 个节点的堆。
如果我们要添加一个节点...
我们将节点的总数加一。现在我们总共有 11 个节点。我们将新的节点总数 (11) 转换为其二进制表示：1011。
使用总节点（1011）的二进制表示，我们去掉了第一个数字。之后，我们使用 011 在树中导航到下一个要插入节点的位置。0 表示向左，1 表示向右。因此，使用 011，我们将向左、向右、向右……这将我们带到下一个要插入的位置。
我们每层检查一个节点，使得时间复杂度 O(log n)
于 2014-01-27T21:02:34.167 回答
6
您不会实现堆IN二叉树，因为堆是二叉树。堆维护以下顺序属性 - 给定节点 V，其父节点大于或等于 V。此外，堆是完全二叉树。我在 uni 上过 ADS 课程，所以稍后我将在答案中为您提供我在 Java 中的堆实现。仅列出您获得的主要方法复杂性：
- 大小() O(1)
- isEmpty() O(1)
- 插入（） O（登录）
- removeMin() O(logn)
- 分钟（） 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);}
}
为您提供 O(logn) 性能的有趣部分是downHeapBubble()andupHeapBubble()方法。我将很快添加关于它们的很好的解释。
upHeapBubble()在向堆中插入新节点时使用。因此，当您插入时，您插入到最后一个位置，然后您需要这样调用upHeapBubble()：
last++;
S[last] = e;
upHeapBubble();
然后将最后一个元素与它的父元素进行比较，如果父元素更大 - 交换：这是完成 max logn 次，其中 n 是节点数。所以这里是登录性能。
对于删除部分 - 您只能删除 min - 最高节点。因此，当您删除它时 - 您必须将它与最后一个节点交换 - 但是您必须维护堆属性并且您必须执行downHeapBubble(). 如果节点大于它的子节点，则与最小的节点交换，依此类推，直到您没有任何子节点或您没有更小的子节点。这可以在最大登录时间完成，因此这里是登录性能。您可以通过在此处查看二叉树图片来解释为什么此操作可以完成最大登录次数
于 2013-08-14T20:23:41.017 回答
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) 中的下一个未占用节点。
谢谢。
于 2013-08-14T20:36:55.300 回答
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(lon n) 性质。与删除类似的事情。
其他操作都是常规操作，并保留其性能特征。
您需要详细信息还是更喜欢自己解决？
如果您想使用链接二叉树，除了左右指针之外没有其他信息，那么我建议您启动至少 100,000 点的赏金。我并不是说这是不可能的（因为我没有数学来证明它），但我是说这几十年来都没有发现（我知道）。
于 2013-08-14T20:24:42.453 回答
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);
}
}
}
于 2014-05-06T21:19:31.077 回答
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 中使用的代码，我修改为使用 2 位数字。如果我们移动到 3 位数字，它将被破坏，它只是为了简单理解堆结构的外观。A修复 3 位数字的方法是将所有内容保持为 3 的倍数。还要感谢 Sesh Venugopal 在 Youtube 上关于堆数据结构的精彩教程
于 2016-08-19T05:38:01.190 回答
-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());
}
于 2015-06-14T05:35:02.750 回答
-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);
}
}
于 2021-02-15T09:37:40.890 回答