Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public void insert(ArrayList<Integer> heap, int val){
heap.add(val);
update(heap, heap.size()-1);
}
private void update(ArrayList<Integer> heap, int index){
if(index==1){
return;
}
if(heap.get(index)<heap.get(index/2)){
int temp = heap.get(index);
heap.set(index, heap.get(index/2));
heap.set(index/2, temp);
update(heap, index/2);
}
}
public void delete(ArrayList<Integer> heap){
if(heap.size()<=1){
return;
}
int temp = heap.get(1);
heap.set(1, heap.get(heap.size()-1));
heap.set(heap.size()-1, temp);
heap.remove(heap.size()-1);
heapify(heap, 1);
}
private void heapify(ArrayList<Integer> heap, int index){
if(index>(heap.size()-1)/2){
return;
}
int indexMin;
if(index*2==heap.size()-1){
indexMin = index*2;
}else{
indexMin = heap.get(index*2)<heap.get(index*2+1)?index*2:index*2+1;
}
if(heap.get(index)>heap.get(indexMin)){
int temp = heap.get(index);
heap.set(index, heap.get(indexMin));
heap.set(indexMin, temp);
heapify(heap, indexMin);
}
}
public ArrayList<Integer> generateHeap(int[] array){
ArrayList<Integer> heap = new ArrayList<>();
heap.add(-1);
for(int i=0;i<array.length;i++){
insert(heap, array[i]);
}
return heap;
}
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if(k>input.length){
ArrayList<Integer> list = new ArrayList<>();
return list;
}
ArrayList<Integer> heap = generateHeap(input);
ArrayList<Integer> result = new ArrayList<>();
for(int i=0;i<k;i++){
result.add(heap.get(1));
delete(heap);
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] array = {4,5,1,6,2,7,3,8};
ArrayList list = solution.GetLeastNumbers_Solution(array, 10);
System.out.println();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.