第2章 排序算法（续原博）

算法（续原博）"/>

第2章 排序算法（续原博）

6.优先队列---复杂度（时间logn,空间1）

a.基础算法（堆实现，数组表示完全二叉树）

package com.Page1;public class MaxPQ<Key extends Comparable<Key>>{ //用堆实现的优先队列，其中堆用完全二叉树表示，树节点用数组表示//注意，本代码实现的是最大堆，即优先级最高的元素是值最大的元素private Key[] pq;//节点private int N;//节点个数,注意节点从1开始MaxPQ(int max) //刚开始就指定最多的节点数{pq=(Key[])new Comparable[max+1];}public void insert(Key v){N++;pq[N]=v;swim(N);}public Key max(){return pq[1];}public Key delMax(){Key max=pq[1];pq[1]=pq[N--];pq[N+1]=null;//防止对象游离sink(1);return max;}public boolean isEmpty(){return N==0;}public int size(){return N;}public boolean less(int p,int q) //注意，参数是两者的下标{return pq[p]pareTo(pq[q])<0;}public void exch(int p,int q){Key x=pq[p];pq[p]=pq[q];pq[q]=x;}private void swim(int k) //上浮函数{while(k>1&&less(k/2,k)){exch(k/2,k);k/=2;}}private void sink(int k) //下沉函数{while(k*2<=N){int j=2*k;if(j<N&&less(j,j+1)) j++; //如k节点有右儿子且右儿子大于左儿子，则下标指向右儿子if(!less(k,j)){break;}exch(k,j);k=j;}}public static void main(String[] args){MaxPQ<Integer> pq=new MaxPQ<Integer>(5); //注意需要诸如<Integer>这样的类型限制pq.insert(2);pq.insert(3);pq.insert(1);pq.insert(10);pq.insert(5);System.out.println("max is "+pq.max());System.out.println("delmax is "+pq.delMax());System.out.println("max is "+pq.max());}}

b.索引最小堆算法

理解过程参考.html

package com.Page1;public class IndexMinPQ<Item extends Comparable<Item>>{ //索引最小优先队列//有三个数组int[] pq;//存储pq完全二叉树的节点相关的元素值Item[] element;//索引,存储的是真正的元素值，相当于键值（因为后续的比较大小同样还是用element中的值来比较）int[] qp;//用来反过来pq的对应关系，即以pq的元素值作为下标，对应元素是其在pq中的下标int N=0;IndexMinPQ(int max){pq=new int[max+1];qp=new int[max+1];element=(Item[]) new Comparable[max+1];}public void insert(int k,Item x){//三个数组都要修改pq[++N]=k;element[k]=x;qp[k]=N;//修正堆swim(N);}public void change(int k,Item item){element[k]=item;//修正堆,上浮和下沉swim(k);sink(k);}public boolean contains(int k){return qp[k]!=0;}public void delete(int k){//修改三个数组element[k]=null;int pqIndex=qp[k];//待删除元素的索引在pq中的下标qp[k]=0;if(pqIndex==N)//若删除的是最后一个元素{pq[pqIndex]=0;N--;return;}pq[pqIndex]=0;//将待删除元素与最后一个元素交换exch(pqIndex,N--);//调整堆swim(pqIndex);sink(pqIndex);}public Item min(){return element[pq[1]];}public int minIndex(){return pq[1];}public int delMin(){int minIndex=pq[1];//修改三个数组qp[minIndex]=0;element[minIndex]=null;if(N==1)//若目前只有一个元素{pq[1]=0;N--;return minIndex;}pq[1]=0;//将待删除元素与最后一个元素交换exch(1,N--);//调整堆sink(1);return minIndex;}public boolean isEmpty(){return N==0;}private void swim(int k) //上浮函数{while(k>1&&less(k,k/2)){exch(k/2,k);k/=2;}}private void sink(int k) //下沉函数{while(k*2<=N){int j=2*k;if(j<N&&less(j+1,j)) j++; //如k节点有右儿子且右儿子大于左儿子，则下标指向右儿子if(less(k,j)){break;}exch(k,j);k=j;}}public boolean less(int p,int q) //注意，参数是两者的下标{return element[pq[p]]pareTo(element[pq[q]])<0;}public void exch(int p,int q){//改变的是pq和qp数组，element数组不变int x=pq[p];pq[p]=pq[q];pq[q]=x;int y=qp[pq[p]];qp[pq[p]]=qp[pq[q]];qp[pq[q]]=y;}public static void main(String[] args){IndexMinPQ<Integer> pq=new IndexMinPQ<Integer>(5);pq.insert(1, 2);pq.insert(2, 12);pq.insert(3, 100);pq.insert(4, 4);System.out.println("minIndex is "+pq.minIndex()+" min is "+pq.min());pq.change(1, 10);System.out.println("minIndex is "+pq.minIndex()+" min is "+pq.min());pq.delete(4);System.out.println("minIndex is "+pq.minIndex()+" min is "+pq.min());}}

c.利用算法b实现多向归并（Page205)

package com.Page1;import edu.princeton.cs.algs4.In;public class Multiway {public static void merge(In[] streams){int N=streams.length;IndexMinPQ<String> pq=new IndexMinPQ<String>(N+1);//we'll see,队列大小只需要Nfor(int i=0;i<N;i++)//首先，每个输入流都先读一个字符串{if(!streams[i].isEmpty())pq.insert(i+1, streams[i].readString());//注意插入的字符串的索引正是其所属的输入流的下标,注意索引从1开始}while(!pq.isEmpty()){//找到并删除最小的元素，并向队列加入其所属输入流的下一个字符串System.out.print(pq.min()+" ");int Index=pq.delMin();if(!streams[Index-1].isEmpty()){pq.insert(Index, streams[Index-1].readString());}}}public static void main(String[] args){In[] streams=new In[3];streams[0]=new In("d://11.txt");streams[1]=new In("d://12.txt");streams[2]=new In("d://13.txt");merge(streams);}}

d.堆排序（即给定任意数组，得到排序后的数组）

堆排序包括两个过程：“有序堆的构造”和“依次获得元素及之后的下沉操作”。

ps.我实现得有点复杂，主要在于我多设置了两个辅助函数，赋值来赋值去的。。实际上可以使用更少的代码实现。

更简单的代码可参见大神的博客.html

package com.Page1;public class Heap { //堆排序,大顶堆public static void sort(Comparable[] a1){//由于堆使用的数组下标是从1开始的，所以这里对a数组做处理Comparable[] a=new Comparable[a1.length+1];for(int i=0;i<a1.length;i++){a[i+1]=a1[i];}int N=a.length-1;//实际上就是堆的元素个数//a数组就是原始的乱序堆//首先将该乱序堆变为有序堆（大顶堆，而不是a数组有序，只是此时的堆满足大小有序状态）for(int i=N/2;i>=1;i--){sink(a,i,N);}//依次交换最大值与数组末尾值，并减少待处理的数组长度，使得最后得到排序好的数组while(N>1){exch(a,1,N--);//因为这里比较特殊，考虑到sink函数中N的定义是a数组的长度，而此时我们的a数组需要考虑的长度正逐渐变短//所以这里我麻烦一点，再新建一个辅助函数Comparable[] aux=new Comparable[N+1];for(int i=1;i<=N;i++)aux[i]=a[i];sink(aux,1,N);//用的是辅助函数参与sink方法//之后再把sink完的aux的值赋回给a数组for(int i=1;i<=N;i++)a[i]=aux[i];}//再将a数组中的数赋回给a1数组for(int i=1;i<=a1.length;i++){a1[i-1]=a[i];}}private static void sink(Comparable[] a,int p,int q) //从p到q进行下沉操作{for(int i=p;i<=q;i++){sink(a,i);}}private static void sink(Comparable[] a,int k) //下沉函数{int N=a.length-1;while(k*2<=N){int j=2*k;if(j<N&&less(a,j,j+1)) j++; //如k节点有右儿子且右儿子大于左儿子，则下标指向右儿子if(!less(a,k,j)){break;}exch(a,k,j);k=j;}}public static boolean less(Comparable[] a,int p,int q) //注意，参数是两者的下标{return a[p]pareTo(a[q])<0;}public static void exch(Comparable[] a,int p,int q){Comparable x=a[p];a[p]=a[q];a[q]=x;}public static void main(String[] args){Integer a[]= {100,1,2,6,5,4,3};Heap.sort(a);//注意可以使用Comparable接口的是Integer而不是intfor(int i=0;i<a.length;i++){System.out.print(a[i]+" ");}}}