利用堆实现排序和解决topk问题之Java实现

古城微笑少年丶 2023-07-25 06:11 20阅读 0赞

# 利用堆实现排序和解决topk问题之Java实现 #

如下图，将一个数组转化堆，有如下性质

*  所有父节点的值小于或等于两个子节点的值(最小堆)
 *  如果有左子树，那么左子树的位置是2i+1，如果有右子树，右子树的位置是2i+2
 *  只有数组下标小于或等于 【数组长度 / 2 - 1】 的元素有孩子结点

![format_png][]

堆排序实现思想：

> 不断构造堆，交换堆顶与末尾未排序的每一个元素，直到全部都排完。

topK问题实现思想：

> 创建一个大小为k的数组，对该数组构造堆。遍历数组中剩余的元素，依次与构建好的堆项元素比较，如果满足条件(大于或小于)则替换堆顶元素并重新构造堆。

public class HeapDemo {
        public static void main(String[] args){     
            //最小堆实现从大到小排序
            int[] arrSort = {90,3,60,6,7,2,89,100,33,5};        
            MinHeap heap1 = new MinHeap(arrSort);
            for(int i = arrSort.length - 1;i > 0; i --){
                //把最小的元素移到末尾
                heap1.swap(0, i);
                //重新构造最小堆
                heap1.buildHeap(i);
            }
            //打印排序后的数组
            for(int i = 0; i < arrSort.length;i ++){
                System.out.println(arrSort[i]);
            }       
            
            //最小堆实现topK
            int[] arrTopK = {90,44,60,6,71,2,38,13,33,5};
            int k = 3;
            //创建一个大小为k的数组
            int[] data = new int[k];
            for(int i = 0; i < k; i ++){
                data[i] = arrTopK[i];
            }       
            MinHeap heap = new MinHeap(data);       
            for(int i = k; i < arrTopK.length; i ++){
                //如果大于堆顶的元素则替换顶并重新构造
                if(arrTopK[i] > heap.getRoot()) heap.setRoot(arrTopK[i]);           
            }       
            //打印最大的k个数
            for(int i = 0; i < k; i ++){
                System.out.println(data[i]);
            }
        }
    
        //最小堆类
        static class MinHeap{
            private int[] data;
            public MinHeap(int[] data){
                this.data = data;
                buildHeap(data.length);
            }
    
            public void buildHeap(int heapSize){
                for(int i = heapSize / 2 - 1; i >= 0;i --){
                    heapify(i, heapSize);
                }
            }
    
            public void heapify(int index,int heapSize){
                int right = right(index);
    
                int left = left(index);
    
                int min = index;
    
                if(right < heapSize && data[right] < data[min]) min = right;
    
                if(left < heapSize && data[left] < data[min]) min = left;
    
                if(min == index) return;
    
                swap(index,min);
    
                heapify(min,heapSize);
            }
    
            private int right(int index){
                //右儿子的下标
                return (index + 1) << 1;
            }
    
            private int left(int index){
                //左儿子的下标
                return ((index + 1) << 1) - 1;
            }
    
            public void swap(int index1,int index2){
                int tmp = data[index1];
                data[index1] = data[index2];
                data[index2] = tmp;
            }
    
            public int getRoot(){
                return data[0];
            }
    
            public void setRoot(int root){
                data[0] = root;
                heapify(0, data.length);
            }
        }
    }

参考文章：  
[http://blog.csdn.net/xiao\_\_gui/article/details/8687982][http_blog.csdn.net_xiao_gui_article_details_8687982]  
[http://blog.csdn.net/kimylrong/article/details/17150475][http_blog.csdn.net_kimylrong_article_details_17150475]

[format_png]: /images/20230528/7954cc80be964772b514b2005ccec85e.png
[http_blog.csdn.net_xiao_gui_article_details_8687982]: http://blog.csdn.net/xiao__gui/article/details/8687982
[http_blog.csdn.net_kimylrong_article_details_17150475]: http://blog.csdn.net/kimylrong/article/details/17150475