더미 로 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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.