ヒープソートの実装について。ソートできないです。

ヒープソートの実装をしたくてプログラムを組んだのですが動かないです。どこをどう直せばよいでしょうか？
[3,1,4,1,5,9,2,6,5,3,3]
上記の結果になりソートできません。

Java
1package exer3.sort;
2
3import java.util.ArrayList;
4import java.util.Comparator;
5import java.util.StringJoiner;
6
7public class HeapSort <T> {
8    
9    private ArrayList<T> data;
10    private Comparator<T> cmp;
11
12    public static <E> void sort(ArrayList<E> a, Comparator<E> c){
13        HeapSort<E> s = new HeapSort<>(a, c);
14        s.hsort();
15    }
16
17    private HeapSort(ArrayList<T> a, Comparator<T>c) {
18        data = a;
19        cmp = c;
20    }
21
22    private void hsort() {
23        // 今のところ中身なし.プライベートメソッドの動作確認のコードをココに記入可
24        enter(9);
25        extract(9);
26        printHeap();
27    }
28
29    private void swap(int a, int b) {
30        T tmp = data.get(a);
31        data.set(a, data.get(b));
32        data.set(b, tmp);
33    }
34
35    private int parent(int n){
36        return ( n - 1 )/2;
37    }
38
39    private int rightChild(int n){
40        return 2 * n + 2;
41    }
42
43    private int leftChild(int n){
44        return 2 * n + 1;
45    }
46
47    private void enter(int n){
48        T a,b;
49        int pv = parent(n);
50        a = data.get(n);
51        b = data.get(pv);
52        while(pv >= 0){
53            if(cmp.compare(data.get(pv) , data.get(n)) < 0){
54                swap(n,pv);
55                n = pv;
56                pv = parent(n);
57            }
58            else
59                break;
60        }
61    }
62
63    private void extract(int n){
64        
65        if(data.size() != 0){
66            T ret = data.get(0);
67            data.set(0, data.get(n));
68            int v = parent(n); int lv = leftChild(n); int rv = rightChild(n);
69        while(lv < data.size()){
70            if( rv < data.size()  && cmp.compare(data.get(v) , data.get(lv)) < 0 && cmp.compare(data.get(lv) , data.get(rv)) >= 0){
71                swap(v, lv);    v = lv; 
72            }
73            else if(rv < data.size() && cmp.compare(data.get(v) , data.get(rv)) < 0 && cmp.compare(data.get(lv) , data.get(rv)) < 0 ){
74                swap(v,rv);
75                v = rv;
76            }
77            else if(rv == data.size() && cmp.compare(data.get(v) , data.get(lv)) < 0){
78                swap(v,rv);
79                v = lv;
80            }
81            else
82                break;
83                lv = 2*v +1;
84                rv = 2*v +2;
85        }
86        data.add(ret);
87        }
88    
89    }
90
91    private void printHeap() {
92        StringJoiner j = new StringJoiner(",");
93        for (T e : data)
94        j.add(e.toString());
95        System.out.println("[" + j.toString() + "]");
96    }
97}
98
99
100
101
102
103package exer3.sort.tester;
104
105import exer3.sort.HeapSort;
106import java.util.ArrayList;
107import java.util.StringJoiner;
108
109public class TesterHS01 extends Tester {
110    public static void main(String[] args) {
111        ArrayList<Integer> a = new ArrayList<>();
112        a.add(3); a.add(1); a.add(4); a.add(1); a.add(5);
113        a.add(9); a.add(2); a.add(6); a.add(5); a.add(3);
114        HeapSort.sort(a, (i1, i2) -> Integer.compare(i1, i2));
115    }
116}
117
118
119
120
121
122package exer3.sort.tester;
123
124import java.util.ArrayList;
125import java.util.StringJoiner;
126
127public class Tester {
128    public static <T> void print(ArrayList<T> lst) {
129        StringJoiner j = new StringJoiner(",");
130        for (T e : lst)
131            j.add(e.toString());
132        System.out.println("[" + j.toString() + "]");
133    }
134
135    public static <T> void printA3(ArrayList<Integer> o,
136                            ArrayList<String> k, ArrayList<T> v) {
137        for(Integer i : o)
138            System.out.printf("[%d] %s\t%s\n",
139                                i, k.get(i), v.get(i).toString());
140    }
141}
142

y_waiwai

2020/08/09 09:29

動かないとはどういうふうになるんでしょうか詳しく書きましょう

Zuishin

2020/08/09 09:45

> public static <E> void sort(ArrayList<E> a, Comparator<E> c){ > HeapSort<E> s = new HeapSort<>(a, c); > s.hsort(); > } ソート結果を捨ててるからですね。

frere

2020/08/09 10:16

コンストラクタが間違っているということですか？

frere

2020/08/09 10:17

どう直せばいいですか？

行動規範の内容に同意します

回答2件

ベストアンサー

ヒープソートのアルゴリズムがきちんと実装できていないためソートできていません。
途中経過を出すなりして何が間違っているのか確認しながら修正してください。

メソッドenter()はおそらくUp-Heapを実装していると思いますが、正しく動作しています。
ただし使い方が間違っています。
メソッドextract()はDown-Heapのつもりでしょうが、data.size()を使っていてはヒープソートの実装はできません。
そして、同じく使い方が間違っています。

それぞれ使い方は下記の様な形の使い方になるかと。

private void hsort() {
    //0～i-1番目まではヒープ済みとし、i番目をヒープに追加する。
    for(int i=1;i<data.size();i++){
        enter(i);
    }
    printHeap();　//ここまでは正しくヒープ木が出力される。

    //i～N番目まではソート済みとし、i番目にヒープの最大値を置き、Down-Heapする。
    for(int i=data.size()-1;i==0;i--){
        extract(i);
    }
    printHeap();
}

投稿2020/08/09 12:10

Kaleidoscope

総合スコア257

frere

2020/08/09 14:43

private void extract(int n){ if(n != 0){ T ret = data.get(0); data.set(0, data.get(n)); int v = parent(n); int lv = leftChild(n); int rv = rightChild(n); while(lv < n){ if( rv < n && cmp.compare(data.get(v) , data.get(lv)) < 0 && cmp.compare(data.get(lv) , data.get(rv)) >= 0){ swap(v, lv); v = lv; } else if(rv < n && cmp.compare(data.get(v) , data.get(rv)) < 0 && cmp.compare(data.get(lv) , data.get(rv)) < 0 ){ swap(v,rv); v = rv; } else if(rv == n && cmp.compare(data.get(v) , data.get(lv)) < 0){ swap(v,rv); v = lv; } else break; lv = 2*v +1; rv = 2*v +2; } data.add(ret); } } 上記にしてみたんですけど治らないです [9,6,5,5,3,3,2,1,4,1] [9,6,5,5,3,3,2,1,4,1]

行動規範の内容に同意します

java
1import java.util.ArrayList;
2import java.util.Comparator;
3
4class HeapSort<T> {
5    private ArrayList<T> data;
6    private Comparator<T> cmp;
7
8    public static <E> void sort(ArrayList<E> a, Comparator<E> c){
9        HeapSort<E> s = new HeapSort<>(a, c);
10        s.hsort();
11    }
12
13    private HeapSort(ArrayList<T> a, Comparator<T> c) {
14        data = a;
15        cmp = c;
16    }
17
18    private void hsort() {
19		int i = 0, n = data.size();
20		while (++i < n) enter(i);
21		while (--i > 0) extract(i);
22        printHeap();
23    }
24
25    private void swap(int a, int b) {
26        T tmp = data.get(a);
27		data.set(a, data.get(b));
28		data.set(b, tmp);
29    }
30
31    private int parent(int n)     { return (n-1) / 2; } 
32    private int rightChild(int n) { return 2 * n + 2; }
33	private int leftChild(int n)  { return 2 * n + 1; }
34
35    private void enter(int n) {
36        int pv = parent(n);
37        while (pv > 0 && cmp.compare(data.get(pv), data.get(n)) < 0) {
38			swap(n, pv);
39			n = pv;
40			pv = parent(n);
41        }
42    }
43
44    private void extract(int n) {
45		swap(0, n);
46        int m = 0, v = 0, lv = leftChild(v), rv = rightChild(v);
47        while (lv < n) {
48            if (cmp.compare(data.get(v), data.get(lv)) < 0)
49				m = lv;
50            if (rv < n && cmp.compare(data.get(m), data.get(rv)) < 0)
51                m = rv;
52            if (m == v) break;
53            swap(v, m);
54			v = m;
55			lv = leftChild(v);
56			rv = rightChild(v);
57        }
58    }
59
60    private void printHeap() { System.out.println(data); }
61}
62
63class Main {
64    public static void main(String[] args) {
65        ArrayList<Integer> a = new ArrayList<>();
66        a.add(3); a.add(1); a.add(4); a.add(1); a.add(5);
67        a.add(9); a.add(2); a.add(6); a.add(5); a.add(3);
68        HeapSort.sort(a, (i1, i2) -> Integer.compare(i1, i2));
69    }
70}