使用二叉树实现堆
之前在Stack Exchange中已经提出过这个问题，但没有得到答复。
链接到前面提到的问题： 二进制堆通过二叉树结构实现
如何在二叉树中实现堆。 要实现堆，了解最后一个填充节点和第一个未占用节点非常重要。 这可以在树的级别排序中完成，但是时间复杂度将是O（n）以便找到第一个未占用的节点。 那么，如何在O（logn）中的二叉树中实现堆？
谢谢Shekhar
要使用具有O（log n）时间复杂度的二叉树实现堆，您需要将节点总数存储为实例变量。
假设我们有一堆总共10个节点。
如果我们要添加一个节点……
我们将节点总数增加1。 现在我们有11个节点。 我们将新的节点总数（11）转换为其二进制表示：1011。
利用总节点（1011）的二进制表示，我们摆脱了第一个数字。 然后，我们使用011在树中导航到下一个位置以插入节点.0表示向左移动，1表示向右移动。 因此，使用011，我们将向左，向右，向右走……这将我们带到下一个要插入的位置。
我们检查了每个级别一个节点，使得时间复杂度为O（log n）
您不会实现堆IN二进制树，因为堆是二叉树。 堆维护以下顺序属性 – 给定节点V，其父级大于或等于V.此外，堆是完整的二叉树 。 我在uni学习了ADS课程，所以我将在后面的答案中为您提供Java实现。 只列出您获得的主要方法复杂性：
- 尺寸（）O（1）
- isEmpty（）O（1）
- insert（）O（logn）
- removeMin（）O（logn）
- min（）O（1）
这是我的Heap.java文件：
public class Heap> { 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()和upHeapBubble()方法。 我很快就会对它们加上很好的解释。
将新节点插入堆时使用upHeapBubble() 。 所以当你插入插入到最后一个位置然后你需要像这样调用upHeapBubble() ：
last++; S[last] = e; upHeapBubble();
然后将最后一个元素与它的父元素进行比较，如果父元素更大 - swap：这是完成max logn times，其中n是节点数。 这就是登录性能。
对于删除部分 - 您只能删除min - 最高节点。 所以当你删除它时 - 你必须将它与最后一个节点交换 - 但是你必须保持堆属性，你必须做一个downHeapBubble() 。 如果节点大于它与最小节点的子交换，依此类推，直到您没有留下任何子节点或者您没有较小的子节点。 这可以在最大logn时间完成，因此这里有登录性能。 您可以通过查看二进制树图片来解释自己为什么可以通过最大日志时间完成此操作
使用树实现堆积
我正在回答我自己的问题，它采用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）中找到下一个未占用的节点。
谢谢。
假设您想使用链接二进制树，没有指向父节点的指针，那么我能想到的唯一解决方案就是保持每个节点中子节点数的计数器。
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点的赏金。 我不是说这是不可能的（因为我没有数学certificate它），但我说这几十年来都没有发现（我知道）。
我的堆实现
public class Heap > { 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); } } }
二叉树可以用数组表示：
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
用法：
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()); }
import java.util.ArrayList; import java.util.List; /** * @author Harish R */ public class HeapPractise> { private List heapList; public List getHeapList() { return heapList; } public void setHeapList(List 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 heap = new HeapPractise<>(); for (int i = 0; i < 32; i++) { heap.insert(i); } System.out.println(heap.getHeapList()); List> nodeArray = new ArrayList<>(heap.getHeapList() .size()); for (int i = 0; i < heap.getHeapList().size(); i++) { Integer heapElement = heap.getHeapList().get(i); Node node = new Node (heapElement); nodeArray.add(node); } for (int i = 0; i < nodeArray.size(); i++) { int leftNodeIndex = (2 * i) + 1; int rightNodeIndex = (2 * i) + 2; Node node = nodeArray.get(i); if (leftNodeIndex <= heap.getHeapList().size() - 1) { Node leftNode = nodeArray.get(leftNodeIndex); node.left = leftNode; } if (rightNodeIndex <= heap.getHeapList().size() - 1) { Node 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 node = new Node (heapElement); nodeArray.add(node); } for (int i = 0; i < nodeArray.size(); i++) { int leftNodeIndex = (2 * i) + 1; int rightNodeIndex = (2 * i) + 2; Node node = nodeArray.get(i); if (leftNodeIndex <= heap.getHeapList().size() - 1) { Node leftNode = nodeArray.get(leftNodeIndex); node.left = leftNode; } if (rightNodeIndex <= heap.getHeapList().size() - 1) { Node rightNode = nodeArray.get(rightNodeIndex); node.right = rightNode; } } BTreePrinter.printNode(nodeArray.get(0)); } } public class Node> { Node 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 > void printNode(Node root) { int maxLevel = BTreePrinter.maxLevel(root); printNodeInternal(Collections.singletonList(root), 1, maxLevel); } private static > void printNodeInternal( List> 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> newNodes = new ArrayList>(); for (Node 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 > int maxLevel(Node node) { if (node == null) return 0; return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1; } private static boolean isAllElementsNull(List list) { for (Object object : list) { if (object != null) return false; } return true; } }
请注意，BTreePrinter是我在Stackoverflow中长期使用的代码，我修改为使用2位数字。如果我们移动到3位数字，它将被破坏，它只是为了简单理解堆结构的外观.A修复3位数字是为了将所有内容保持为3的倍数。同样归功于Sesh Venugopal在Youtube上关于Heap数据结构的精彩教程