北大青鳥北京，通州北大青鳥校區學術部講解：Java的排序之“堆排序”

北京北大青鳥通州校區學術部老師講解：什么是堆排序？

北京北大青鳥專家解答：堆排序是另一種選擇排序方法,它是樹型選擇排序的改進,優勢是使用的輔助空間較少,僅需要一個元素用于空間交換。（北京北大青鳥）

堆排序包括兩個步驟 (1)初始堆(堆的定義：(1)堆是一個完全二叉樹(2)根結點的值或者大于左右子樹的值或者小于左右子樹的值(3)左右子樹也是一個堆)（北京北大青鳥）

(2)調整堆(當初始小頂堆之后，堆頂元素是最小的元素，取出最小的元素與最后一個元素相交換，再把剩下n-1個元素調整成堆,依次調整直到1為止)（北京北大青鳥）

public abstract class PriorityQueue {
  private Object[] heap;
  private int size;
  private int maxSize;
  /** Determines the ordering of objects in this priority queue.  Subclasses
    must define this one method. */
  protected abstract boolean lessThan(Object a, Object b);
  /** Subclass constructors must call this. */
  protected final void initialize(int maxSize) {
    size = 0;
    int heapSize = maxSize + 1;
    heap = new Object[heapSize];
    this.maxSize = maxSize;
  }
  /**
   * Adds an Object to a PriorityQueue in log(size) time.
   * If one tries to add more objects than maxSize from initialize
   * a RuntimeException (ArrayIndexOutOfBound) is thrown.
   */
  public final void put(Object element) {
    size++;
    heap[size] = element;
    upHeap();
  }
  /**
   * Adds element to the PriorityQueue in log(size) time if either
   * the PriorityQueue is not full, or not lessThan(element, top()).
   * @param element
   * @return true if element is added, false otherwise.
   */
  public boolean insert(Object element){
    if(size < maxSize){
      put(element);
      return true;
    }
    else if(size > 0 && !lessThan(element, top())){
      heap[1] = element;
      adjustTop();
      return true;
    }
    else
      return false;
   }
  /** Returns the least element of the PriorityQueue in constant time. */
  public final Object top() {
    if (size > 0)
      return heap[1];
    else
      return null;
  }
  /** Removes and returns the least element of the PriorityQueue in log(size)
    time. */
  public final Object pop() {
    if (size > 0) {
      Object result = heap[1];     // save first value
      heap[1] = heap[size];     // move last to first
      heap[size] = null;     // permit GC of objects
      size--;
      downHeap();      // adjust heap
      return result;
    } else
      return null;
  }
  /** Should be called when the Object at top changes values.  Still log(n)
   * worst case, but it's at least twice as fast to

   *  { pq.top().change(); pq.adjustTop(); }
   * 

   *  { o = pq.pop(); o.change(); pq.push(o); }
   * 

  /** Returns the number of elements currently stored in the PriorityQueue. */
  public final int size() {
    return size;
  }
  /** Removes all entries from the PriorityQueue. */
  public final void clear() {
    for (int i = 0; i <= size; i++)
      heap[i] = null;
    size = 0;
  }
  private final void upHeap() {
    int i = size;
    Object node = heap[i];     // save bottom node
    int j = i >>> 1;
    while (j > 0 && lessThan(node, heap[j])) {
      heap[i] = heap[j];     // shift parents down
      i = j;
      j = j >>> 1;
    }
    heap[i] = node;      // install saved node
  }
  private final void downHeap() {
    int i = 1;
    Object node = heap[i];     // save top node
    int j = i << 1;      // find smaller child
    int k = j + 1;
    if (k <= size && lessThan(heap[k], heap[j])) {
      j = k;
    }
    while (j <= size && lessThan(heap[j], node)) {
      heap[i] = heap[j];     // shift up child
      i = j;
      j = i << 1;
      k = j + 1;
      if (k <= size && lessThan(heap[k], heap[j])) {
 j = k;
      }
    }
    heap[i] = node;      // install saved node
  }
}
結束（北京北大青鳥）

相關鏈接：Java的排序之“快速排序”