gpt4 book ai didi

java - 索引为 0 而不是索引 1 的 heapSort 的 maxheap 方法

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:24:02 26 4
gpt4 key购买 nike

我有这段 heapSort 的代码,它工作正常。我还了解当起始 index1 而不是 0algorithm 的工作原理。我的问题是下面的 maxheap 方法本身适用于所有大于零的索引,但不适用于索引 0。但是 Sort 方法调用 index 0 并且 array 得到排序。当 index i = 0 时,对 maxheap 的调用将有 left=2*i=0 和 right=2*i+1=1 ,这导致 ileft0rightindex 1 相同>,表示 rootleft 相同,只有 right 树。这让我感到困惑。这是代码:

public class HeapSort 
{
private static int heapSize;

/* Sort Function */
public static void sort(int arr[])
{
heapify(arr);
System.out.println("arrays is "+Arrays.toString(arr));
for (int i = heapSize; i > 0; i--)
{
swap(arr,0, i);
heapSize = heapSize-1;
maxheap(arr, 0);
}
}

/* Function to build a heap */
public static void heapify(int arr[])
{
heapSize = arr.length-1;
for (int i = heapSize/2; i >= 0; i--)
maxheap(arr, i);
System.out.println("finished maxheap");
}

/* Function to swap largest element in heap */
public static void maxheap(int arr[], int i)
{
//heapSize = arr.length-1;// comment this out if you use sort method since `heapSize` is defined at heapfy method
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= heapSize && arr[left] > arr[i])
max = left;
if (right <= heapSize && arr[right] > arr[max])
max = right;
//System.out.printf("i is %s; left is %s; right is %s; max is %s%n",i,left,right,max);
if (max != i)
{
swap(arr, i, max);
maxheap(arr, max);
}
}

/* Function to swap two numbers in an array */
public static void swap(int arr[], int i, int j)
{
//System.out.println("called");
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

/* Main method */

public static void main(String[] args)
{
System.out.println("Heap Sort Test\n");
/* Call method sort */
int[] arr = {34,5,6,712,90};
sort(arr);
System.out.println("\nElements after sorting ");
System.out.println(Arrays.toString(arr));

/* Call method maxheap; make sure you comment in heapSize=arr.length in the method */
int[] arr2 = {2,1,3};
maxheap(arr2, 1);
//maxheap(arr2,0) will not work, i.e gives same arr2 as output
System.out.println(Arrays.toString(arr2));
}

}

编辑:这两个博客使用相同的代码:sanfoundry.com/java-program-implement-heap-sort,
sciencetechpedia.blogspot.com/2012/11/heap-sort-using-java.html

最佳答案

如果你的数组的起始索引=0,计算左子索引和右子索引的方法应该是这样的:

private static int getLeftCh (int index) {
return index * 2 + 1;
}
private static int getRightCh (int index) {
return index * 2 + 2;
}


[我的 Heapsort 是这样的]

public class HeapSort {

// Heap sort the givenArray.
// Time complexity = O(nlgn).
// From max to min.
private static int getLeftCh (int index) {
return index * 2 + 1;
}
private static int getRightCh (int index) {
return index * 2 + 2;
}
private static void exchange (int[] givenArray, int firstIndex, int secondIndex) {
int tempElem = givenArray[firstIndex];
givenArray[firstIndex] = givenArray[secondIndex];
givenArray[secondIndex] = tempElem;
}
private static void minHeapify (int[] givenArray, int size, int index) {
int left = getLeftCh(index);
int right = getRightCh(index);
int minIndex = index;
if (left < size && givenArray[left] <= givenArray[index]) minIndex = left;
else minIndex = index;
if (right < size && givenArray[right] < givenArray[minIndex]) minIndex = right;
if (index != minIndex) {
// Exchange the givenArray[index] and the givenArray[minIndex].
exchange(givenArray, index, minIndex);
// Do recrusion on from minIndex.
minHeapify (givenArray, size, minIndex);
}
}
private static void buildMinHeap (int[] givenArray) {
int size = givenArray.length;
for (int i = (size / 2 - 1); i >= 0; i --) {
// Do min-heapify on the i.
minHeapify (givenArray, size, i);
}
}
public static void heapSortFromMaxToMin (int[] givenArray) {
int size = givenArray.length;
// Build the max heap.
buildMinHeap(givenArray);

// Do the max-heapify on the remaining part of the minheap.
for (int i = size - 1; i >= 0; i --) {
// Move the current first elem back to the last one among the current scope.
exchange (givenArray, 0, size - 1);
// Do minHeapify on the remaining part of the heap from the index = 0.
minHeapify (givenArray, (-- size), 0);
}
}

// Show array.
public static void showArray (int[] givenArray) {
int size = givenArray.length;
for (int i = 0; i < size; i ++)
System.out.print(String.format("%-6d", givenArray[i]));
System.out.println();
}


// Main method to test.
public static void main (String[] args) {
// Test data: {5, 4, 8, 0, 2, -5, 8, 0}.
int[] givenArray = {5, 4, 8, 0, 2, -5, 8, 0};

// Test the heap sort on the givenArray, from max to min.
heapSortFromMaxToMin (givenArray);
showArray(givenArray);
}
}

关于java - 索引为 0 而不是索引 1 的 heapSort 的 maxheap 方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21838044/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com