2
該程序需要一個n長度的數組，並使用heapsort將最小的k個元素返回。我已經從數組中獲得了k個最小的元素，但我現在已經嘗試了幾個小時，以便按升序打印它們。基於父親和兒子，幾乎完整的二叉樹正在構建。如果有人能幫我弄清楚我需要做什麼，我將不勝感激。獲取heapsort打印升序
此外，這是一項家庭作業，我不要求代碼來解決它。我合法地被難住了，並且只想設置在正確的路徑上以使其正常工作。預先感謝您的任何意見。
編輯 - 我種它必須按升序排列輸出，用於基本的測試我目前得到： 5,6,31,34,29，
import java.lang.*;
import java.util.*;
public class heap {
/*
* Definitions of the parameters
* 1) tree: the array where the sweeping window is implemented
* 2) newEle: the new element to insert
* 3) pos: where to insert the new element initially.
* note it does not mean newEle is going to
* stay at pos after this function
* 4) increment
* a) true: insert newEle, that is all
* b) false: insert newEle and then remove the root
*/
static void insertHeapTreeAt(int[] tree, int newEle,
int pos, boolean increment) {
int temp;
//place first element in, no need to start tree yet
if (tree[0] == 0) {
tree[0] = newEle;
}
//increment is true, sliding window isn't full yet
if (increment == true) {
tree[pos] = newEle;
//create tree
createTree(tree);
} else {
//increment is false, if larger than root do nothing
//place in pos (being k+1), then swap with root.
//then createTree slides everything so father > son
if (newEle < tree[0]) {
tree[pos] = newEle;
temp = tree[0];
tree[0] = tree[pos];
tree[pos] = 0;
createTree(tree);
}
}
//Then need to compare the root down the tree to check for father>=son
}
static void createTree(int[] tree) {
int i, father, son;
for (i = 1; i < tree.length; i++) {
int leaf = tree[i];
son = i;
father = (son - 1)/2;
while (son > 0 && tree[father] < tree[son]) {
tree[son] = tree[father];
tree[father] = leaf;
son = father;
father = (son - 1)/2;
}
}
// sort(tree);
}
static void sort(int[] tree) {
int father, larger, temp;
//father = 0;
for (int i = tree.length - 1; i > 0; i--) {
//No need to bubble down bc only 1 node
if (i - 1 == 0) {
break;
}
//two nodes, root and son
if (i - 1 == 1) {
//then the larger son has to be left (index = 1)
larger = 1;
} else {
//compare left/right sons for larger
larger = (tree[1] > tree[2]) ? 1 : 2;
}
//bubble down from root
father = 0;
while (tree[father] < tree[larger]) {
temp = tree[father];
tree[father] = tree[larger];
tree[larger] = temp;
father = larger;
if (2 * father + 1 > i - 1) {
break; //no son, rofl
} else if (2 * father + 1 > i - 1) {
larger = 2 * father + 1; //only left son
} else {
larger = (tree[2 * father + 2] > tree[2 * father + 1]) ? 2 * father + 2
: 2 * father + 1;
}
}
}
}
static void sortAscending(int[] x){
int father, son, temp;
for (int i = 0; i < x.length-1; i++) {
son = i;
father = (son - 1)/2;
//while (son > 0 && x[father] > x[son]) {
while(x[father] > x[son]){
temp = x[son];
x[son] = x[father];
x[father] = temp;
son = father;
father = (son - 1)/2;
}
}
}
/*
* get the smallest k elements in array x in O(nlogn) time, where
* n is the size of array x.
*
* It is supposed to return an array, containing the smallest k elements
* in the increasing order.
*/
static int[] getSmallestK(int x[], int k) {
if (k > x.length) {
return null;
}
int[] result = new int[k + 1];
// use the first k elements in x to construct an
// almost complete binary tree, where father>=sons
result[0] = x[0];
for (int i = 1; i < k; i++) {
insertHeapTreeAt(result, x[i], i, true);
}
// for each element in the rest of array x,
// insert it in the almost complete binary tree, and then
// remove the root in the tree.
for (int i = k; i < x.length; i++) {
insertHeapTreeAt(result, x[i], k, false);
}
// now the first k elements in result are the smallest k elements in x
// sort the first k elements in result in O(klogk) time
sortAscending(result);
//sort(result);
return result;
}
public static void main(String[] args) {
// Basic Testing
int[] data = {31, 44, 64, 5, 61,
43, 6, 88, 59, 90,
39, 97, 77, 62, 99,
34, 57, 53, 60, 29};
int[] smallestK = getSmallestK(data, 5);
for (int i = 0; i < 5; i++) {
System.out.print(smallestK[i] + ",");
}
System.out.println();
// More Complete Testing
Random random = new Random();
List<Integer> numsList = new ArrayList<Integer>();
int[] numsArray = new int[1000];
for (int i = 0; i < 1000; i++) {
int rand = 0;
do {
rand = random.nextInt(1000);
} while (numsList.contains(rand));
numsList.add(rand);
numsArray[i] = rand;
}
Collections.sort(numsList);
int[] smallest100 = getSmallestK(numsArray, 100);
for (int i = 0; i < 100; i++) {
System.out.print(smallest100[i] + ",");
}
System.out.println();
for (int i = 0; i < 100; i++) {
System.out.print(numsList.get(i) + ",");
}
for (int i = 0; i < 100; i++) {
if (numsList.get(i) != smallest100[i]) {
throw new RuntimeException("Error");
}
}
}
}