C# 基于堆的优先队列算法

优先队列由一个基于堆的完全二叉树表示，存储于数组pq[1...N]中，pq[0]没有使用。在insert()中，我们将N加一并把新元素添加在数组最后，然后用swim()恢复堆的秩序。在delMax()中，我们从pq[1]中得到需要返回的元素，然后将pq[N]移动到pq[1]，将N减一并用sink()恢复堆的秩序。同时我们还将不再使用的pq[N 1]设为null，以便系统回收它所占用的空间。

命题：对于一个含有N个元素的基于堆的优先队列，插入元素操作只需不超过（lgN 1）次比较，删除最大元素的操作需要不超过2lgN次比较。

证明：由上一个命题可知，两种操作都需要在根结点和堆底之间移动元素，而路径的长度不超过lgN。对于路径上的每个结点，删除最大元素需要两次比较（除了堆底元素），一次用来找出较大的子结点，一次用来确定该子结点是否需要上浮。

对于需要大量混杂的插入和删除最大元素操作的典型应用来说，上面的命题意味着一个重要的性能突破。使用有序或是无序数组的优先队列的初级实现总是需要线性时间来完成其中一种操作，但基于堆的实现则能够保证在对数时间内完成它们。这种差别使得我们能够解决以前无法解决的问题。

堆上的优先队列操作如下图

package com.huazhou;

import android.app.Application;
import android.test.ApplicationTestCase;

/**
 * Testing Fundamentals
 */
public class ApplicationTest extends ApplicationTestCase {
    public ApplicationTest（） {
        super（Application.class）;
    }
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-12-15 07:21  Algorithms-master\
     文件          13  2015-12-15 07:21  Algorithms-master\README.md
     目录           0  2015-12-15 07:21  Algorithms-master\TXTFiles\
     文件          32  2015-12-15 07:21  Algorithms-master\TXTFiles\shell.txt
     文件      726569  2015-12-15 07:21  Algorithms-master\TXTFiles\tale.txt
     文件          22  2015-12-15 07:21  Algorithms-master\TXTFiles\tiny.txt
     文件         496  2015-12-15 07:21  Algorithms-master\TXTFiles\tinyBatch.txt
     文件          36  2015-12-15 07:21  Algorithms-master\TXTFiles\tinyCG.txt
     文件         138  2015-12-15 07:21  Algorithms-master\TXTFiles\tinyDG.txt
     文件          63  2015-12-15 07:21  Algorithms-master\TXTFiles\tinyG.txt
     文件         277  2015-12-15 07:21  Algorithms-master\TXTFiles\tinyTale.txt
     文件         141  2015-12-15 07:21  Algorithms-master\TXTFiles\words3.txt
     目录           0  2015-12-15 07:21  Algorithms-master\app\
     文件           7  2015-12-15 07:21  Algorithms-master\app\.gitignore
     文件         578  2015-12-15 07:21  Algorithms-master\app\build.gradle
     文件         653  2015-12-15 07:21  Algorithms-master\app\proguard-rules.pro
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\androidTest\
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\androidTest\java\
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\androidTest\java\com\
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\androidTest\java\com\huazhou\
     文件         342  2015-12-15 07:21  Algorithms-master\app\src\androidTest\java\com\huazhou\ApplicationTest.java
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\main\
     文件         279  2015-12-15 07:21  Algorithms-master\app\src\main\AndroidManifest.xml
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\main\res\
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\main\res\mipmap-hdpi\
     文件        3418  2015-12-15 07:21  Algorithms-master\app\src\main\res\mipmap-hdpi\ic_launcher.png
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\main\res\mipmap-mdpi\
     文件        2206  2015-12-15 07:21  Algorithms-master\app\src\main\res\mipmap-mdpi\ic_launcher.png
     目录           0  2015-12-15 07:21  Algorithms-master\app\src\main\res\mipmap-xhdpi\
     文件        4842  2015-12-15 07:21  Algorithms-master\app\src\main\res\mipmap-xhdpi\ic_launcher.png
............此处省略97个文件信息