北大青鸟北京，通州北大青鸟校区学术部讲解：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的排序之“快速排序”