通過二叉樹結構實現的二進制堆

Question

對於一項任務，我們被指示創建一個通過二進制堆實現的優先級隊列，而不使用任何內置類，並且我通過使用數組來存儲排隊的對象。但是，我有興趣學習如何通過使用實際的樹結構來實現另一個隊列，但是這樣做時我遇到了一些問題。

我將如何跟蹤要執行插入和刪除的節點？我試過使用鏈接列表，它會在插入每個節點時追加 - 從第一個列表節點開始添加新的子節點，並從相反的一端刪除。然而，當元素重新排列在樹中時，這會分崩離析，因爲孩子被添加到錯誤的位置。

編輯︰也許我應該澄清 - 我不知道我將如何能夠找到最後佔領和第一空置的葉子。例如，我總是能夠告訴最後插入的葉子，但是如果我要刪除它，當我下次刪除該項目時，我怎麼知道要刪除哪一片葉子？插入同樣如此 - 我怎麼知道在當前葉子有兩個孩子之後，哪一片葉子跳到下一個葉子？

Answer 1

二叉堆的樹實現使用complete tree [或幾乎完整的樹：除了最深的樹之外，每個級別都是滿的]。
你總是'知道'哪一個是最後一個被佔用的葉 - 你從[刪除]中刪除[並且在它改變後是O（logn），所以它不是問題]，並且你總是'知道'被佔用的葉子，在其中添加元素[並且再次修改它在改變之後也是O（logn）]。

算法思想很簡單：
插入：插入元素到第一個非佔據葉，並使用heapify [篩選了]這個元素得到堆中的正確位置。

delete_min：用最後被佔用的葉子替換第一個元素，並刪除最後被佔用的葉子。然後，heapify [篩選]堆。

編輯：注意delete()可以做任何元素，不僅頭部，但是 - 找到你想用最後一片葉子會爲O（n），這將使得這款運算昂貴的更換部件。因此，delete()方法[除了head]通常不是堆數據結構的一部分。

Answer 2

我真的想做這個近十年。最後坐下來寫下來。任何想要它的人都可以使用它。我從Quora創始人的啓發下重新學習堆。顯然他被問到你會如何找到K在他的Google手機屏幕的n個點附近得分接近。顯然，他的答案是使用Max Heap並存儲K值，並在堆大小超過K後刪除最大元素。該方法非常簡單，最差在大多數排序情況下，情況爲nlog K，優於n^2。這裏是代碼。

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

    } 

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

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

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是我在某處＃1長了回代碼，我修改的，如果我們移動到3個數字與2位numbers.It使用將被打破，這是隻爲簡單的理解3位數字的修正是將所有數據保持爲3的整數倍。 同時由於Sesh Venugopal在Youtube上針對堆數據結構提供了精彩教程