优先队列

1.优先队列（堆）：堆是一种完全二叉树（完全二叉树insert ，delete时候，这种数据结构能够直接进行自我的调整），二叉堆也叫完全二叉树，使用完全二叉树实现最方便的。

但是完全二叉树并不是堆，这种完全二叉树不得不满足有序性的原理，因此与AVL树一样，对堆（完全二叉树）操作必须让堆满足所有的性质为止因此高度H的完全二叉树有 2^h个节点高度[logN],算法复杂度o(logN)

最小堆性质：满足任意一个节点比其子孙后代小，不同于二叉查找树，不采用二叉查找树的特性在于，如果采用查找树删除最小元素，反复去除左子树节点，让右子树变的偏重

使用完全二叉树的结构最大特点可以使用数组表示不需要使用链表的方式

更加注重的删除操作；堆两个特性及：结构性和有序性

log有序性：从根节点到任一节点的路径上结点保持明显的有序性。

如果采用数组实现的话：

堆性质中数组实现左儿子在2*i位置上右儿子在2*i+1位置上

适用范围：海量数据中求最大的前N位数据，必须重新理解优先队列的删除元素和插入元素

2.性质：采用完全二叉树实现，不需要进行比较，只需要保证树的结构性和有序性不同平衡二叉树（需要对数据进行比较处理），这里保证根节点是最小元

插入过程（insert）采用上滤的策略：插入新位置同其父结点进行比较找到其堆中正确位置

删除过程（）：1.FindMin函数找到数组中最小值，删除只够

  1 package Heap;
  2 
  3 import org.omg.CORBA.portable.UnknownException;
  4 
  5 public class BinaryHeap <AnyType extends Comparable <? super AnyType>>  {
  6     
  7     /*java 语言 编写最小堆得实现*/
  8     
  9     /*堆 私有性质：堆得容量 ，数组的类型AnyType代替*/
 10     private int currentSize;
 11     private AnyType [] array; //the heap array
 12     
 13     private static final int DEFAULT_CAPACITY=10;
 14     public void makeEmpty()
 15     {
 16         currentSize=0;
 17         for(int i=0;i<array.length;i++)
 18             array[i]=null;
 19     }
 20     
 21     public boolean isEmpty()
 22     {
 23         if (currentSize>0)
 24                 return false;
 25         else
 26                 return true;
 27                     
 28     }
 29     /*构造函数初始化：1.默认10 2.根据输入量开辟数组 
 30      * 3 二叉堆是一些项的初始集合构造合成 因此对其进行调整让其符合堆得性质*/
 31     public BinaryHeap()
 32     {
 33         this(DEFAULT_CAPACITY);
 34     }
 35     
 36     @SuppressWarnings("unchecked")
 37     public BinaryHeap(int capacity)
 38     {
 39         
 40         currentSize=0;
 41         array=(AnyType[]) new Comparable[capacity+1];
 42     }
 43     
 44     /*将无序的二叉树调整形成堆*/
 45     @SuppressWarnings("unchecked")
 46     public BinaryHeap(AnyType [] item)
 47     {
 48         currentSize=item.length;
 49         array=(AnyType []) new Comparable[((currentSize+2)*11/10)];
 50         array[0]=null;
 51         
 52         for(int i=0 ;i<item.length;i++)
 53             array[i+1]=item[i];
 54         
 55         
 56         buildheap();//采用下过滤将无序二叉树进行调整
 57         
 58     }
 59     
 60     public void buildheap()
 61     {
 62             for(int i=currentSize/2;i>0;i--)
 63                  precolateDown(i);
 64     }
 65     @SuppressWarnings("unchecked")
 66     public void insert(AnyType x)
 67     {
 68         if(currentSize==array.length-1)
 69         {
 70             enlargeArray(array.length*2+1);
 71         }
 72         
 73         /*采用上滤策略进行插入，对于插入元素与其父结点比较，从底层到顶层
 74          * array[0]位置存放当前插入元素，当做咲兵*/
 75         int hole=++currentSize;
 76         
 77         for(array[0]=x;  x.compareTo(array [hole/2])<0;hole/=2)
 78             array[hole]=array[hole/2];
 79         
 80         array[hole]=x;
 81     }
 82     
 83     @SuppressWarnings("unchecked")
 84     public void  enlargeArray(int newSize)
 85     {
 86         AnyType []old=array;
 87         
 88         array=(AnyType[]) new Comparable[newSize+1];
 89         
 90         for(int i=0;i<old.length;i++)
 91             array[i]=old[i];
 92         
 93     }
 94     
 95     public AnyType  FindMin()
 96     {
 97         if(isEmpty())
 98             return null;
 99         return array[1];
100     }
101     
102     public AnyType deletMin()
103     {
104         /*从堆中进行弹出,将最后一个元素提到最首位置上采用下过滤策略进行堆得调整
105          * 采用下过滤方法；相反从顶层向底层依次调整顺序*/
106         if(isEmpty())
107             throw new UnknownException(null);
108         AnyType minItem=FindMin();
109         
110         array[1]=array[currentSize--];
111         precolateDown(1);
112         
113         return minItem;
114     }
115     
116     @SuppressWarnings({ "unchecked", "rawtypes" })
117     public void precolateDown(int hole)
118     {
119         int child;
120         AnyType tmp=array[hole];
121         
122         for(;hole*2<=currentSize;hole=child)
123         {
124             child=hole*2;
125             /*前部分保证有左右两子节点 ；挑选出子节点最小元素*/
126             if(child!=currentSize &&  array[child+1].compareTo(array[child]) <0)
127                 child++;/*指向子节点中较小值*/
128             if(  array[child].compareTo(tmp)<0)
129                         array[hole]=array[child];
130             else
131                 break;
132                             
133         }
134         array[hole]=tmp;
135     }
136     
137     public void Println()
138     {
139         for (int i=0;i<array.length;i++)
140             System.out.println(i+1 + "位置上： " + array[i]);
141     }
142       public static void main( String [ ] args )
143       {
144           int itemnum=15;
145           Integer [] item=new Integer [itemnum];
146           
147           item[0]=150;item[1]=80;item[2]=40;item[3]=30;item[4]=10;item[5]=70;
148           item[6]=110;item[7]=100;item[8]=20;item[9]=90;item[10]=60;item[11]=50;
149           item[12]=120;item[13]=140;item[14]=130;
150           
151           for(int i=0;i<item.length;i++)
152               System.out.println(item[i]);
153           BinaryHeap <Integer> H =new BinaryHeap<Integer>(item);
154           H.Println();
155       }
156 }


/*测试：原有的无序集合进行堆得建立，直接采用下过滤方式进行处理*/
150
80
40
30
10
70
110
100
20
90
60
50
120
140
130
1位置上： null
2位置上： 10
3位置上： 20
4位置上： 40
5位置上： 30
6位置上： 60
7位置上： 50
8位置上： 110
9位置上： 100
10位置上： 150
11位置上： 90
12位置上： 80
13位置上： 70
14位置上： 120
15位置上： 140
16位置上： 130
17位置上： null
18位置上： null

二.二叉堆的推广----d堆（所有节点有d个儿子，树变浅但是insert算法变成 logd（N），删除时候找出d个儿子最小值） 4-堆比二叉堆运行速度更快

堆实现过程中：最明显缺点将两个堆合成（merge）成一个堆，堆得merge

1.左式堆：支持有效的合并使用链式数据结构，不同于二叉堆，趋向于非常不平衡。性质：左儿子零路径长>=右儿子零路径长，偏向向左增加深度，为了合并

零路径长：从X到不具有两个儿子节点的最短路径，npx（null）=-1，只有一个节点或者零个节点的npx=0；

堆左式堆合并过程理解：http://www.07net01.com/program/33962.html

合并过程中： 1.遵守最小堆原则，任意结点比子结点的值小

　　　　　　 2. 原则：根值大的堆与根植小的堆右子堆进行合并，合并完成之后不符合左子堆条件必须要交互子树

　　　　　　3.H1只有一个节点 H1没有右子堆 H1有右子堆

　　　　　　4. 编程过程记录合并堆得零路径长

  1 package Heap;
  2 
  3 import java.util.LinkedList;
  4 
  5 import org.omg.CORBA.portable.UnknownException;
  6 
  7 public class LeftistHeap <AnyType extends Comparable <? super AnyType>>{
  8     /*运用链式数据结构，树结构不用数组存储数据*/
  9         
 10     private static class Node<AnyType> 
 11     {
 12         AnyType element;/*the data in the node*/
 13         Node<AnyType> right;Node<AnyType> left;
 14         int npl;/*null path length*/        
 15             
 16         Node(AnyType theelement)
 17            {
 18                this(theelement,null,null);
 19            }
 20            
 21        Node(AnyType theelement,Node<AnyType> lt,Node<AnyType> rt)
 22            {
 23                element=theelement;
 24                left=lt;right=rt;npl=0;
 25            }
 26     }
 27 
 28 
 29     private Node<AnyType> root;
 30     
 31     public LeftistHeap()
 32     {
 33         root=null;
 34     }
 35     
 36     public boolean isEmpty()
 37     {
 38         return root==null;
 39     }
 40     public void makeEmpty()
 41     {
 42         root=null;
 43     }
 44     
 45     public void insert( AnyType x)
 46     {
 47         /*将x与 新的链表结点合并在一起*/
 48         root=merge(new Node<> (x),root);
 49         
 50     }
 51     public void merge(LeftistHeap<AnyType> rhs)
 52     {
 53         /*将其他不同左式堆与现有左式堆进行合并*/
 54         if(this==rhs)
 55             return ;
 56         root=merge(root,rhs.root);
 57         rhs.root=null;
 58     }
 59     
 60     private Node<AnyType> merge(Node<AnyType> h1,Node<AnyType> h2)
 61     {
 62         /*分为三种情况*/
 63         if(h1==null)
 64             return h2;
 65         if(h2==null)
 66             return h1;
 67         /*原则：根植大的堆与根植小的堆得右子堆进行合并*/
 68         if(h1.element.compareTo(h2.element)<0)
 69             return meger1(h1,h2);
 70         else
 71             return meger1(h2,h1);
 72         
 73         
 74     }
 75     
 76     private Node<AnyType> meger1(Node<AnyType>h1,Node<AnyType>h2)
 77     {
 78         if(h1.left==null)
 79              h1.left=h2;
 80         else
 81         {
 82             h1.right=merge(h1.right,h2);
 83             if(h1.left.npl < h1.right.npl)
 84                 swapChildren(h1);
 85             
 86             h1.npl=h1.right.npl+1;
 87             
 88         }
 89         return h1;
 90     }
 91     
 92     private  void swapChildren(Node<AnyType > t)
 93     {
 94         Node<AnyType> tmp=t.left;
 95         t.left=t.right;
 96         t.right=tmp;
 97         
 98     }
 99     public AnyType findMin()
100     {
101         if( isEmpty( ) )
102             throw new UnknownException(null );
103         return root.element;
104     }
105     public AnyType deletMin()
106     {
107         if( isEmpty( ) )
108             throw new UnknownException(null );
109         AnyType minItem=root.element;
110         
111         root=merge(root.left,root.right);
112         
113         return minItem;
114     }
115     
116     
117     public  void levelOrder(Node<AnyType> P)
118     {
119         /*层次遍历过程要用队列*/
120         LinkedList <Node<AnyType>> queue=new LinkedList<>();
121         queue.add((Node<AnyType>) P);
122     
123         while(P!=null &&(!queue.isEmpty()))
124         {
125             P=(Node<AnyType>) queue.element();
126             System.out.println("["+P.element+"]");
127             
128             if(P.left!=null) queue.add((Node<AnyType>) P.left);
129             if(P.right!=null) queue.add((Node<AnyType>) P.right);
130             queue.remove();
131         }
132         
133         
134     }
135     public static void main(String[] args) {
136         // TODO Auto-generated method stub
137         LeftistHeap <Integer > h=new LeftistHeap<>();
138         LeftistHeap <Integer > H1=new LeftistHeap<>();
139         
140         Integer array []=new Integer[8];
141         array[0]=3;array[1]=10;array[2]=8;array[3]=21;array[4]=14;array[5]=17;array[6]=23;array[7]=26;
142            
143         for(int i=0;i<8;i++)
144             H1.insert(array[i]);
145         
146         H1.levelOrder(H1.root);
147         //h.levelOrder(h.root);
148         
149     }
150 
151 }

结果显示：

[3]
[8]
[10]
[21]
[14]
[17]
[23]
[26]

　　结构如下显示：符合左式堆条件：左子树零路径长大于等于右子树零路径长；