HeapSort理論？

Question

我沒有使用HeapSort對已經填充的數組進行排序，但是在數組填滿時使用HeapSort。

對於最小值位於頂部的堆，我的理解是當您向堆中插入新值時，您檢查了父節點以查看新子是否較大。如果你不做任何事情，如果不是你檢查並交換需要的樹？

，因爲我實現它不工作這是不對的：

public class HeapSort{ 
static int[] numbers = new int[] { 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; 
static int[] array = new int[16]; 

public static void main(String[] args) { 
    for (int i = 1; i < 15; i++) { 
     array[i] = numbers[i]; 
     if (i > 1) 
      sort(i); 
    } 
    for (int i = 1; i < 15; i++) { 
     System.out.println(array[i]); 
    } 
} 

public static void sort(int i) { 
    int parentLocation = i/2; 
    int childLocation = i; 

    int parentValue = array[parentLocation];  
    int childValue = array[childLocation]; 

    if(parentValue > childValue){ 
     array[parentLocation] = childValue; 
     array[childLocation] = parentValue; 
    } 
    if(parentLocation != 1){ 
     sort(parentLocation); 
    } 
    } 
} 

TIA

如果其anyhelp這是輸出的時候我給它1-15落後：

2 
6 
3 
9 
7 
5 
4 
15 
12 
13 
8 
14 
10 
11 

但你們都像我一樣難住！

Answer 1

它看起來像你不整理整個陣列。假設你有10個正確排序的字段，並且你插入了數字。所以你有
- ，1，2，3，4，5，6，7，8，9，11和插入10（應該倒數第二，因爲你從來沒有放任何東西）

現在你的算法比較parentLocation 5（11/2）和childLocation 11的權利？那麼，5小於11，所以沒有任何交換。然後你繼續用輸入5重新排序。

這次你比較parentLocation 2（5/2）和childLocation 5. 2小於5，仍然沒有改變。

直到完成。但是你從來沒有測試過10和11是否按照正確的順序進行測試，所以你開始半途而廢。

最簡單的解決是你的兩個迭代改變

for (int i = 1; i < numbers.length; i++) {...} 
... 
for (int i = 1; i < array.length; i++) {...} 

當你的失蹤在當前的代碼的最後位置。
然後在排序（）的第一行更改爲

int parentLocation = i - 1; 

這樣，你的遞歸檢查檢查整個陣列。 但是，這是常規的排序，沒有什麼heapy一下吧:)

新增完成新的解決方案:) 我敢肯定這是不是最佳的解決方案，但它很容易跟進。我已經用ArrayList替換了目標堆，以便能夠輕鬆地將其縮小。

package se.wederbrand.stackoverflow; 

import java.util.ArrayList; 

public class HeapSort { 
    static int[] numbers = new int[]{0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
    static ArrayList<Integer> heap = new ArrayList<Integer>(); 

    public static void main(String[] args) { 
    // add 0 at the first position 
    heap.add(0); 
    for (int i = 1; i < numbers.length; i++) { 
     heap.add(numbers[i]); 
     if (i > 1) { 
     reheapifyBottomUp(i); 
     } 
    } 
    while (heap.size() > 1) { 
     System.out.println(removeFirstFromHeap()); 
    } 
    } 

    private static int removeFirstFromHeap() { 
    // the value at index 1 should be returned 
    int returnValue = heap.get(1); 

    // the last node is replacing the removed one 
    if (heap.size() > 2) { 
     heap.set(1, heap.remove(heap.size() - 1)); 
     reheapifyTopDown(1); 
    } 
    else { 
     heap.remove(1); 
    } 

    return returnValue; 
    } 

    public static void reheapifyBottomUp(int childLocation) { 
    int parentLocation = childLocation/2; 

    int parentValue = heap.get(parentLocation); 
    int childValue = heap.get(childLocation); 

    if (parentValue > childValue) { 
     heap.set(parentLocation, childValue); 
     heap.set(childLocation, parentValue); 
    } 
    if (parentLocation != 1) { 
     reheapifyBottomUp(parentLocation); 
    } 
    } 

    public static void reheapifyTopDown(int parentLocation) { 
    int childLocation1 = parentLocation * 2; 
    int childLocation2 = childLocation1 + 1; 

    int parentValue = heap.get(parentLocation); 
    int childValue1 = Integer.MAX_VALUE; 
    if (heap.size() > childLocation1) { 
     childValue1 = heap.get(childLocation1); 
    } 
    int childValue2 = Integer.MAX_VALUE; 
    if (heap.size() > childLocation2) { 
     childValue2 = heap.get(childLocation2); 
    } 

    if (childValue1 <= childValue2 && parentValue > childValue1) { 
     // swap them and continue down 
     heap.set(parentLocation, childValue1); 
     heap.set(childLocation1, parentValue); 
     reheapifyTopDown(childLocation1); 
    } 
    else if (childValue2 < childValue1 && parentValue > childValue2) { 
     // swap them and continue down 
     heap.set(parentLocation, childValue2); 
     heap.set(childLocation2, parentValue); 
     reheapifyTopDown(childLocation2); 
    } 
    } 
} 

Answer 2

您在這裏所做的全部工作就是在堆中添加一堆數字（第一眼看起來正確）。該數組包含堆中的值 - 而不是排序列表。要獲得排序列表，在堆排序中，您需要保持彈出最小元素並重新堆積。你錯過了這一步;在開始這個過程之前，你只是打印出最後一堆。

Answer 3

您的排序方法應該更名爲heapify()。你當前的sort（）方法只是重新安排堆。

最小/最大堆永遠不會排序，因此您永遠無法遍歷二進制搜索樹。你將不得不實行類似removeMin（）將從堆和排序剩餘堆取出最上面的元素。