import java.util.ArrayList;
import java.util.List;
class Heap{
private int size;
private List<Integer> heap;
private List<Integer> sorted;
public Heap(int[] nums) {
this.size = nums.length;
int[] newNums = new int[nums.length + 1];
for (int i = 1; i < newNums.length; i++){
newNums[i] = nums[i - 1];
}
for (int i = 1; i < newNums.length / 2 + 1; i++){
int nowIndex = i;
while (nowIndex >= 1){
if (newNums[nowIndex] < newNums[nowIndex * 2] ||
newNums[nowIndex] < newNums[nowIndex * 2 + 1]){
int largeIndex = nowIndex * 2 + 1 >= newNums.length ||
newNums[nowIndex * 2] > newNums[nowIndex * 2 + 1]?
nowIndex * 2:nowIndex * 2 + 1;
int t = newNums[largeIndex];
newNums[largeIndex] = newNums[largeIndex / 2];
newNums[largeIndex / 2] = t;
nowIndex = nowIndex / 2;
}else {
break;
}
}
}
this.heap = new ArrayList<>();
for (int i = 1; i < newNums.length; i++){
this.heap.add(newNums[i]);
}
}
public List<Integer> getHeap() {
return heap;
}
public void heapSort(){
this.sorted = new ArrayList<>();
int sortSize = size + 1;
List<Integer> sortHeap = new ArrayList<>();
sortHeap = getNewList(this.heap, sortHeap);
while (sortHeap.size() >= 2){
int index = 1;
Integer root = sortHeap.get(index);
int last = sortHeap.remove(sortHeap.size() - 1);
this.sorted.add(root);
while (index * 2 < sortHeap.size()){
index = index * 2 + 1 >= sortHeap.size() ||
sortHeap.get(index * 2) > sortHeap.get(index * 2 + 1)?
index * 2:index * 2 + 1;
sortHeap.set(index / 2, sortHeap.get(index));
}
if (sortHeap.size() >= 2) {
sortHeap.set(index, last);
}
}
}
public List<Integer> getSorted() {
heapSort();
return sorted;
}
public List<Integer> getNewList(List<Integer> list1, List<Integer> list2){
list2.add(0);
list2.addAll(list1);
return list2;
}
}