聊聊堆Heap和二叉堆的实现和特性

复制// Java  import java.util.Arrays;  import java.util.NoSuchElementException;  public class BinaryHeap {      private static final int d = 2;      private int[] heap;      private int heapSize;      /**       * This will initialize our heap withdefaultsize.       */      public BinaryHeap(int capacity) {          heapSize = 0;          heap = new int[capacity + 1];          Arrays.fill(heap,聊聊 -1);      }      public boolean isEmpty() {          return heapSize == 0;      }      public boolean isFull() {          return heapSize == heap.length;      }      private int parent(int i) {          return (i - 1) / d;      }      private int kthChild(int i, int k) {          return d * i + k;      }      /**       * Inserts new element into heap       * Complexity: O(log N)       * As worst case scenario, we need to traverse till the root       */      public void insert(int x) {          if (isFull()) {              throw new NoSuchElementException("Heap is full, No space to insert new element");          }          heap[heapSize] = x;          heapSize ++;          heapifyUp(heapSize - 1);      }      /**       * Deletes element atindex x       * Complexity: O(log N)       */      publicintdelete(int x) {          if (isEmpty()) {              throw new NoSuchElementException("Heap is empty, No element to delete");          }          int maxElement = heap[x];          heap[x] = heap[heapSize - 1];          heapSize--;         heapifyDown(x);          return maxElement;      }      /**       * Maintains the heap property while inserting an element.       */      private void heapifyUp(int i) {          int insertValue = heap[i];          while (i > 0 && insertValue > heap[parent(i)]) {              heap[i] = heap[parent(i)];              i = parent(i);          }          heap[i] = insertValue;      }      /**       * Maintains the heap property while deleting an element.       */      private void heapifyDown(int i) {          int child;          inttemp = heap[i];          while (kthChild(i, 1) < heapSize) {              child = maxChild(i);              if (temp >= heap[child]) {                  break;              }              heap[i] = heap[child];              i = child;          }          heap[i] = temp;      }      private int maxChild(int i) {          int leftChild = kthChild(i, 1);          int rightChild = kthChild(i, 2);          return heap[leftChild] > heap[rightChild] ? leftChild : rightChild;      }      /**       * Prints all elements of the heap       */      public void printHeap() {          System.out.print("nHeap = ");          for (int i = 0; i < heapSize; i++)              System.out.print(heap[i] + " ");          System.out.println();      }      /**       * This method returns the max element of the heap.       * complexity: O(1)       */      publicint findMax() {          if (isEmpty())              throw new NoSuchElementException("Heap is empty.");          return heap[0];      }      publicstatic void main(String[] args) {          BinaryHeap maxHeap = new BinaryHeap(10);          maxHeap.insert(10);          maxHeap.insert(4);          maxHeap.insert(9);          maxHeap.insert(1);          maxHeap.insert(7);          maxHeap.insert(5);          maxHeap.insert(3);          maxHeap.printHeap();          maxHeap.delete(5);          maxHeap.printHeap();          maxHeap.delete(2);          maxHeap.printHeap();      }  }  1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.96.97.98.99.100.101.102.103.104.105.106.107.108.109.110.111.112.113.114.115.116.117.118.119.120.121.122.123.124.125.126.127.128.129.130.131.132.133.134.135.136.137.138.139.140.141.142.143.144.145.146.147.148.149.150.151.152.153.154.155.

本文地址：http://www.bhae.cn/html/165d7499760.html