堆排序及优先级队列Java实现

落日映苍穹つ 2022-09-30 06:49 216阅读 0赞

# 堆排序 #

之前的一篇关于《编程珠玑》的读书笔试介绍过优先队列与堆排序的一些内容（[http://blog.csdn.net/megustas\_jjc/article/details/52049845][http_blog.csdn.net_megustas_jjc_article_details_52049845]），近期进行算法的复习的时候，想到了对于之前堆排序的一些优化和想用Java对其进行一次实现，故写了这篇文章。  
此处不同于之前文章的算法，不必先构造出堆，再一个个进行“删除”，此处直接原地构造堆和对堆进行排序，其核心思想就是每次可以构造一个小堆，两个小堆构造一个大堆（如果一个结点的两个子结点已经是堆了，那么在该结点上调用sink()函数调整下，可以将其变成一个堆）……该方法的一个最大优点就是只要扫描数组元素的半，因为可以跳过大小为1的子堆。

import java.util.Arrays;
    
    /**
     * Created by Megustas on 2017/3/19.
     */
    public class Heapsort {
        
        public static void sort(int[] array){
            //建立堆，使目标数组堆有序
            int N = array.length;
            for(int k = N/2;k >= 1;k--){
                sink(array,k,N);
            }
            //进行堆排序
            while (N>1){
                swap(array,1,N--);
                sink(array,1,N);
            }
    
        }
        private static boolean less(int[] pq, int i, int j) {
            return pq[i-1]<pq[j-1];
        }
        private static void swap(int[] array,int i,int j){
            int temp = array[i-1];
            array[i-1] = array[j-1];
            array[j-1] = temp;
        }
        private static void sink(int[] array,int i,int j){
            while (2*i<=j){
                int k = 2*i;
                if(k<j&&less(array,k,k+1)) k++;
                if(!less(array,i,k)) break;
                swap(array,i,k);
                i = k;
            }
        }
        public static void main(String args[]){
            int[] array = {
       4,2,5,3,1,7,5};
            Heapsort.sort(array);
            System.out.println(Arrays.toString(array));
        }
    }

注意：函数less，swap中的参数表示数组中的第几个元素，因此在函数的具体实现部分，回进行减一操作，例如第length个元素是a\[length\]

# 优先队列 #

/*
    优先队列：实现插入元素和删除最大元素的功能
     */
    public class MaxPQ {
        private int[] pq;
        private int N = 0;//存储于pq[1..N]中，pq[0]没有使用
        public MaxPQ(int maxN){
            pq = new int[maxN+1];
        }
        public int size(){
            return N;
        }
        public boolean isEmpty(){
            return N==0;
        }
        public void insert(int key){
            pq[++N] = key;
            swim(N);//插入新元素，进行调整，使之满足堆的要求
        }
        public int deleteMax(){
            int max = pq[1];
            swap(1,N--);
            sink(1);//删除元素之后需要重新调整堆的结构
            return max;
        }
        //辅助方法
        private void swap(int i,int j){
            int temp = pq[i];
            pq[i] = pq[j];
            pq[j] = temp;
        }
        private void swim(int k){
            while (k>1&&pq[k]>pq[k/2]){
                swap(k/2,k);
                k = k/2;
            }
        }
        private void sink(int k){
            while (2*k<N){
                int j = 2k;
                if(pq[2k]<pq[2*k+1]) j++;
                if(pq[k]>pq[j]) break;
                swap(k,j);
                k = j;
            }
        }
    }

用堆实现的优先队列在现代应用中越来越重要，因为它能在插入操作和删除最大元素操作混合的动态场景中保证对数级别的运行时间，是最优的利用时间与空间的方法。例如处理一些大数据时，无法排序（甚至无法全部装入内存），例如需要从10亿个元素中选出最大的十个？如何解决，对10亿个元素排序吗？如果有什么idea欢迎留言讨论

[http_blog.csdn.net_megustas_jjc_article_details_52049845]: http://blog.csdn.net/megustas_jjc/article/details/52049845