2
이 프로그램은 n 길이의 배열을 사용하고 힙을 사용하여 가장 작은 k 요소를 다시 꺼냅니다. 배열에서 k 번째로 작은 요소를 얻었지만 지금 오름차순으로 인쇄하려면 몇 시간 동안 노력했습니다. 거의 완벽한 이진 트리가 아버지 아들에 따라 올바르게 구축됩니다. 누군가 내가 내가해야 할 일을 알아내는 것을 도울 수 있다면 크게 감사 할 것입니다.힙 배열을 오름차순으로 인쇄하십시오.
또한 과제 과제이며 해결할 코드를 요청하지 않습니다. 나는 합법적으로 곤란을 겪었고 제대로 작동하기 위해서는 올바른 길을 택해야합니다. 모든 입력에 대해 미리 감사드립니다. -
편집 나는 종류의 내가 현재 무엇입니까 기본적인 테스트를 위해, 오름차순으로 출력을 가지고, 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");
}
}
}
}