더미 로 top k 문제 해결

2825 단어 데이터 구조
해결 방향
     1. 작은 지붕 더 미 를 구축 하면 지붕 요 소 는 현재 k 개 요소 중에서 가장 작은 요소 입 니 다.
     2. 후속 요 소 는 순서대로 쌓 인 요소 와 비교 하고 쌓 인 요소 보다 작 으 면 next
     3. 쌓 아 올 리 는 요소 보다 크 면 이 요 소 를 쌓 아 올 리 고 다시 쌓 습 니 다.
소스 코드
package dataStructures.tree.heap;

/**
 *      top k  
 *          ,                (     )        
 *       ,        , top k  ,       ,        
 */
public class Topk {
    public static void main(String[] args) {
        int[] data_test = {0,2,4,6,8,6,4,23,55,1};
        Topk.Heap heap = new Topk().new Heap(4);
        for (int i = 1; i < data_test.length; i++) {
            heap.insert(data_test[i]);
        }
        heap.printAll(heap.data, heap.count);
    }
    
    /**
     * 
     * @author victory
     * @date 2019 2 19    10:56:19
     * @Description     
     */
    public class Heap {
        private int[] data;//    
        private int capacity;//   
        private int count;//           

        public Heap(int capacity) {
            this.capacity = capacity;
            this.data = new int[capacity+1];
            this.count = 0;
        }
        
        /**
         *        
         * @param value
         */
        public void insert(int value) {
            if (count < capacity) {
                count++;
                data[count] = value;
                int i = count;
                while (i/2 > 0 && data[i/2] > data[i]) {
                    swap(data, i, i/2);
                    //         2  ,    
                    i >>= 1;
                }
            } else {
                if (value <= data[1]) return;
                data[1] = value;
                printAll(data, count);
                heapify();
                printAll(data, count);
            }
        }

        //            
        private void heapify() {
            int i = 1;
            while (true) {
                int minPos = i;
                if (i * 2 <= count && data[i*2] < data[i]) minPos = i*2;
                if (i * 2 + 1 <= count && data[i*2+1] < data[minPos]) minPos = i*2+1;
                if (minPos == i) break;
                swap(data, i, minPos);
                i = minPos;
            }
        }
        
        private void swap(int[] data, int index1, int index2) {
            int tmp = data[index1];
            data[index1] = data[index2];
            data[index2] = tmp;
        }
        
        //         
        public void printAll(int[] data, int count) {
            for (int i = 1; i <= count; i++) {
                System.out.print(data[i] + ",");
            }
            System.out.println();
        }
    }
}

github 주소
     https://github.com/zuolovezhai/Data-Structures-Algorithms/commit/5b625500886eff764b78affd385a0790ad389dfb

좋은 웹페이지 즐겨찾기