ヒープソート理論？

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 rightを比較しますか？さて、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++) {...} 

にあなたの2回の繰り返しを変更することです。
はその後

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（）と、残りのヒープをソートのように実装する必要があります。