1 package sorts;  2   3 import java.util.ArrayList;  4 import java.util.List;  5 import java.util.Random;  6   7 public class PriorityQueue
     
      > { // min-heap  8     private List
      
        heap = new ArrayList<>();  9     private static final int ROOT_INDEX = 0; 10     private static final int PRE_ROOT_INDEX = ROOT_INDEX - 1; 11     public void offer(T obj) { 12         heap.add(obj);//在最后增加一个元素 13         int index = heap.size() - 1;//最后一个元素的索引 14         while (index > ROOT_INDEX) {
   //在堆中加一个元素后,调整堆使其再成为一个堆 15             index = stepUpHeap(index);//上浮 16         } 17     } 18     private int stepUpHeap(int index) { 19         int parentIndex = parent(index);//获取父节点的索引 20         T element = heap.get(index); 21         T parent  = heap.get(parentIndex); 22         if (parent.compareTo(element) > 0) { //父节点大于儿子节点,交换 23               heap.set(parentIndex, element); 24               heap.set(index, parent); 25               return parentIndex;  // 跳到父索引 26          } else    27               return ROOT_INDEX; //不需要交换 28     } 29     public T poll() { 30         if (isEmpty()) 31             throw new RuntimeException(); 32         int index = heap.size() - 1;//最后一个元素的索引 33         T least; 34         if(index==0){ 35            least = heap.get(index); 36            heap.remove(index); 37         } 38         else{ 39             T element = heap.get(index);//取最后一个元素 40             least  = heap.get(ROOT_INDEX);//取堆的根元素 41             heap.set(ROOT_INDEX, element);//交换这两个元素 42             heap.set(index, least); 43             heap.remove(index);//删除最后一个元素 44             stepDownHeap(ROOT_INDEX);//下沉调整,使之再次成为堆 45          } 46          return least; 47     } 48     private void stepDownHeap(int index) { 49         int p = index;//parent 50         int lchild = lchild(p);//左子节点 51         T temp = heap.get(p); 52         while(lchild
       
         pq = new PriorityQueue<>(); 98         for (int i = 0; i < 10; i++) { 99             pq.offer(random.nextInt(100));100         }101         for (int i = 0; i < 10; i++) {102             System.out.print(pq.poll() + " ");103         }104     }105 }