-1
好吧，這是我最後的任務之一，當然這給我造成了最大壓力，但讓我無法完成這項任務的唯一方法就是能夠在Heap上應用heapsort，用戶輸入自己的整數值在其中顯示，在這裏一個數組列表，是該代碼：我如何在堆上實現heapSort？
堆propgram工作正常，但在堆排序不能正常工作或我不能在HeapApp類使用它，或者撥打電話吧
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Scanner;
/**
*/
public class Heap<T extends Comparable<T>> {
private ArrayList<T> items;
public Heap() {
items = new ArrayList<T>();
}
private void siftUp() {
int k = items.size() - 1;
while (k > 0) {
int p = (k-1)/2;
T item = items.get(k);
T parent = items.get(p);
if (item.compareTo(parent) > 0) {
// swap
items.set(k, parent);
items.set(p, item);
// move up one level
k = p;
} else {
break;
}
}
}
public void insert(T item) {
items.add(item);
siftUp();
}
private void siftDown() {
int k = 0;
int l = 2*k+1;
while (l < items.size()) {
int max=l, r=l+1;
if (r < items.size()) { // there is a right child
if (items.get(r).compareTo(items.get(l)) > 0) {
max++;
}
}
if (items.get(k).compareTo(items.get(max)) < 0) {
// switch
T temp = items.get(k);
items.set(k, items.get(max));
items.set(max, temp);
k = max;
l = 2*k+1;
} else {
break;
}
}
}
public T delete()
throws NoSuchElementException {
if (items.size() == 0) {
throw new NoSuchElementException();
}
if (items.size() == 1) {
return items.remove(0);
}
T hold = items.get(0);
items.set(0, items.remove(items.size()-1));
siftDown();
return hold;
}
public int size() {
return items.size();
}
public boolean isEmpty() {
return items.isEmpty();
}
public String toString() {
return items.toString();
}
//----------------------------------------------------------------------------------------------------------------------------------------
public class Heapsort<T extends Comparable<T>> {
/**
* Sort the array a[0..n-1] by the heapsort algorithm.
*
* @param a the array to be sorted
* @param n the number of elements of a that have valid values
*/
public void sort(T[] a, int n) {
heapsort(a, n - 1);
}
/**
* Sort the ArrayList list by the heapsort algorithm.
* Works by converting the ArrayList to an array, sorting the
* array, and converting the result back to the ArrayList.
*
* @param list the ArrayList to be sorted
*/
public void sort(ArrayList<T> items) {
// Convert list to an array.
@SuppressWarnings("unchecked")
T[] a = (T[]) items.toArray((T[]) Array.newInstance(items.get(0).getClass(), items.size()));
sort(a, items.size()); // sort the array
// Copy the sorted array elements back into the list.
for (int i = 0; i < a.length; i++)
items.set(i, a[i]);
}
/**
* Sort the array a[0..lastLeaf] by the heapsort algorithm.
*
* @param items the array holding the heap
* @param lastLeaf the position of the last leaf in the array
*/
private void heapsort(T[] items, int lastLeaf) {
// First, turn the array a[0..lastLeaf] into a max-heap.
buildMaxHeap(items, lastLeaf);
// Once the array is a max-heap, repeatedly swap the root
// with the last leaf, putting the largest remaining element
// in the last leaf's position, declare this last leaf to no
// longer be in the heap, and then fix up the heap.
while (lastLeaf > 0) {
swap(items, 0, lastLeaf); // swap the root with the last leaf
lastLeaf--; // the last leaf is no longer in the heap
maxHeapify(items, 0, lastLeaf); // fix up what's left
}
}
/**
* Restore the max-heap property. When this method is called, the max-heap
* property holds everywhere, except possibly at node i and its children. When
* this method returns, the max-heap property holds everywhere.
*
* @param items the array holding the heap
* @param i index of the node that might violate the max-heap property
* @param lastLeaf the position of the last leaf in the array
*/
private void maxHeapify(T[] items, int i, int lastLeaf) {
int left = leftChild(i); // index of node i's left child
int right = rightChild(i); // index of node i's right child
int largest; // will hold the index of the node with the largest element
// among node i, left, and right
// Is there a left child and, if so, does the left child have an
// element larger than node i?
if (left <= lastLeaf && items[left].compareTo(items[i]) > 0)
largest = left; // yes, so the left child is the largest so far
else
largest = i; // no, so node i is the largest so far
// Is there a left child and, if so, does the right child have an
// element larger than the larger of node i and the left child?
if (right <= lastLeaf && items[right].compareTo(items[largest]) > 0)
largest = right; // yes, so the right child is the largest
// If node i holds an element larger than both the left and right
// children, then the max-heap property already held, and we need do
// nothing more. Otherwise, we need to swap node i with the larger
// of the two children, and then recurse down the heap from the larger
// child.
if (largest != i) {
swap(items, i, largest);
maxHeapify(items, largest, lastLeaf);
}
}
/**
* Form array a[0..lastLeaf] into a max-heap.
*
* @param items array to be heapified
* @param lastLeaf position of last valid data in a
*/
private void buildMaxHeap(T[] items, int lastLeaf) {
int lastNonLeaf = (lastLeaf - 1)/2; // nodes lastNonLeaf+1 to lastLeaf are leaves
for (int j = lastNonLeaf; j >= 0; j--)
maxHeapify(items, j, lastLeaf);
}
/**
* Swap two locations i and j in array a.
*
* @param items the array
* @param i first position
* @param j second position
*/
private void swap(T[] items, int i, int j) {
T t = items[i];
items[i] = items[j];
items[j] = t;
}
/**
* Return the index of the left child of node i.
*
* @param i index of the parent node
* @return index of the left child of node i
*/
private int leftChild(int i) {
return 2 * i + 1;
}
/**
* Return the index of the right child of node i.
*
* @param i index of the parent node
* @return the index of the right child of node i
*/
private int rightChild(int i) {
return 2 * i + 2;
}
/**
* For debugging and testing, print out an array.
*
* @param a the array to print
* @param n number of elements of a to print
*/
public void printArray(T[] items, int n) {
for (int i = 0; i < n; i++)
System.out.println(items[i]);
}
}
}
import java.util.Scanner;
public class HeapApp{
/**
* @param args
*/
public static void main(String[] args) {
Heap<Integer> hp = new Heap<Integer>();
Scanner sc = new Scanner(System.in);
System.out.print("Enter next int, 'done' to stop: ");
String line = sc.next();
while (!line.equals("done")) {
hp.insert(Integer.parseInt(line));
System.out.println(hp);
System.out.print("Enter next int, 'done' to stop: ");
line = sc.next();
}
while (hp.isEmpty()) {
//int max = hp.delete();
System.out.println(" " + hp);
}
System.out.println(hp);
System.out.println("After sorting " + hp);
}
}
現在我不要求任何人爲我做這件事，但我只是需要幫助搞清楚如何讓heapsort與堆一起工作請幫助！我試過的最多的是在堆排序方法中設置參數。
我的問題和代碼不是從用戶輸入用於一個這種重複是基於堆和堆排序：
public static void main(String[] args) {
Heap<Integer> hp = new Heap<Integer>();
Scanner sc = new Scanner(System.in);
System.out.print("Enter next int, 'done' to stop: ");
String line = sc.next();
while (!line.equals("done")) {
hp.insert(Integer.parseInt(line));
System.out.println(hp);
System.out.print("Enter next int, 'done' to stop: ");
line = sc.next();
}
而且整個堆使用一個ArrayList實現：
public class Heap<T extends Comparable<T>> {
private ArrayList<T> items;
public Heap() {
items = new ArrayList<T>();
}
的可能的複製（http://stackoverflow.com/questions/33439054/whats-wrong-with-my-heapsort-code） – craigts