使用二叉树实现堆

7 回答

• 1

  我的堆实现

  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);
          }
      }
  }
  

  回复于 2024-04-25T03:40:35+08:00
• 0

  要使用具有O（log n）时间复杂度的二叉树实现堆，您需要将节点总数存储为实例变量 .

  假设我们有10个总节点的堆 .

  如果我们要添加一个节点......

  我们将节点总数增加1 . 现在我们有11个节点 . 我们将新的节点总数（11）转换为其二进制表示：1011 .

  利用总节点（1011）的二进制表示，我们摆脱了第一个数字 . 之后，我们使用011在树中导航到下一个位置以插入节点.0表示向左移动，1表示向右移动 . 因此，对于011，我们会向左走，向右走，向右走...这会将我们带到下一个要插入的位置 .

  我们检查了每个级别一个节点，使得时间复杂度为O（log n）

  回复于 2024-04-25T03:40:35+08:00
• 0

  您不会实现堆IN二进制树，因为堆是二叉树 . 堆维护以下顺序属性 - 给定节点V，其父级大于或等于V.此外，堆完成binary tree . 我在uni有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);}
  }
  

  给你O（logn）性能的有趣部分是 downHeapBubble() 和 upHeapBubble() 方法 . 我很快就会对它们加上很好的解释 .

  将新节点插入堆时使用 upHeapBubble() . 所以当你插入插入到最后一个位置然后你需要像这样调用 upHeapBubble() ：

  last++;
  S[last] = e;
  upHeapBubble();
  

  然后将最后一个元素与它的父元素进行比较，如果父元素更大 - swap：这是完成max logn times，其中n是节点数 . 这就是登录性能 .

  对于删除部分 - 您只能删除min - 最高节点 . 所以当你删除它时 - 你必须将它与最后一个节点交换 - 但是你必须保持堆属性，你必须做一个 downHeapBubble() . 如果节点大于它's child swap with the smallest one and so on until you don' t还有剩下的孩子，或者你没有小孩子 . 这可以在最大logn时间完成，因此这里有登录性能 . 您可以通过查看二叉树图片来解释自己为什么可以通过最大日志时间完成此操作here

  回复于 2024-04-25T03:40:35+08:00
• 3

  HEAP IMPLEMENTATION USING TREE

  我正在回答我自己的问题，它采用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）中找到下一个未占用的节点 .

  谢谢 .

  回复于 2024-04-25T03:40:35+08:00
• 9

  假设您想使用 linked 二叉树，没有指向父节点的指针，那么我能想到的唯一解决方案就是保持每个节点中子节点数的计数器 .

  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)
  }
  

  此策略还 balancer 每个子树每侧的节点数，这是有益的（尽管非常轻微） .

  这是O（log n） . 跟踪插入计数需要一直到屋顶，但这不会改变此操作的O（lon n）性质 . 与删除类似的事情 .

  其他操作是通常的，并保持其性能特征 .

  您是否需要详细信息或更喜欢自己解决？

  如果你想使用一个链接的二叉树，没有除左右指针之外的其他信息，那么我建议你发起至少100,000点的赏金 . 我不是说这是不可能的（因为我没有数学证明它），但我说这几十年都没有发现（我知道） .

  回复于 2024-04-25T03:40:35+08:00
• 26

  二叉树可以用数组表示：

  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());
      }
  

  回复于 2024-04-25T03:40:35+08:00
• 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位数字，它将被破坏，它只是为了简单理解堆结构的外观 . 修复3位数字是为了将所有内容保持为3的倍数 . 同样归功于Sesh Venugopal在Youtube上关于Heap数据结构的精彩教程

  回复于 2024-04-25T03:40:35+08:00