时间戳

首页 > 解决方案 > HeapSort 返回错误的数组（Java）

java - HeapSort 返回错误的数组（Java）

问题描述

我的 HeapSort 返回一个顺序不正确的数组。我的原始数组是 {15, 9, 11, 5, 6, 7}，当运行 heapSort 方法时，我得到这个数组：{15, 11, 9, 6, 7, 5}。

我打印了该方法以查看 maxHeap 做了什么并得到了：{15, 9, 11, 5, 6, 7}，当映射到二叉树中时，它实际上是一个 maxHeap。这让我相信排序方法或 buildMaxHeap 方法有问题。

    public class heaps
    {
    public void maxHeap(int arr[], int index, int n)
    {
    int largest = index;
    n = arr.length;
    int l = (2*index) + 1;
    int r =(2*index) + 2;
    int size = arr.length;                                  

    if ((l < n) && (arr[l] > arr[largest]))             
        {
            largest = l;
        }
    else 
        {
            largest = index;    
        }
    if ((r < size) && arr[r] > (arr[largest]))          
        {
            largest = r;
        }
    if (largest != index)
        {
            int temp = arr[index];
            arr[index] = arr[largest];
            arr[largest] = temp;
            maxHeap(arr, largest, n);
        }
}

public void buildMaxHeap(int arr[])
{
    int n = arr.length; 
    for (int index = (n / 2) - 1; index >= 0; index--)
    {
        maxHeap(arr, index, n);
    }
}

public void sort(int arr[])
{
    int n = arr.length;
    buildMaxHeap(arr);

    for (int index = n - 1; index >= 0; index--)
    {
        int temp = arr[0];
        arr[0] = arr[index];
        arr[index] = temp;
        n = n - 1;                      
        maxHeap(arr, index, 0);
    }   
}

public void printArray(int arr[]) 
{ 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
        System.out.print(arr[i]+" "); 
    System.out.println(); 
}

 public static void main(String[] args)
{
    heaps o = new heaps();

    int array[] = {15, 9, 11, 5, 6, 7};

    heaps.sort(array);
    heaps.printArray(array);
    heaps.maxHeap(array, 0, array.length);
    heaps.printArray(array);
}      
}

标签： javasortingpriority-queueheapsortmax-heap

解决方案

如果我正确理解您的maxHeap方法，则该n参数应该是最大索引。也就是说，maxHeap(arr, index, n)应该在 处取项目arr[index]并将其推下堆，但不超过arr[n].

如果这是真的，那么你的错误就在你的maxHeap方法的第二行：

n = arr.length;

您正在覆盖n您传递的参数的值。

您的sort方法中有此调用：

    maxHeap(arr, index, 0);

因此，您要告诉maxHeap将项目arr[index]向下推，但不能低于arr[0]. 在我看来，这将是一个问题，因为什么都不会动。

您需要花一点时间仔细检查您的代码。使用调试器单步执行是一个很大的帮助。如果您不知道如何使用调试器，那么现在是学习的最佳时机。

推荐阅读