ヒープソート

質問

ヒープへのデータの格納と取り出しを適当な例（データ数が７個）を用いておしえていただけないでしょうか？よろしくおねがいします。

回答No.2

ssr-y6

ヒープソート(二分木ソート)は、まず二分木を親よりも子供のほうが必ず大きいか等しくなるように作っていく。
作り終わったら、一番下の親から順に木の構造を維持しつつ取り出していくことでソートする方法。
　以下が、そのサンプルです。

public class heapsort {

public static void main(String args[]) {

int i, j, k, d[], h[] = {5, 10, 1, 3, 8, 9, 2, 7, 4, 6};
int Parent, Child;

try {
String s[] = args[0].split(",");
d = new int[s.length];
for (i = 0; i < s.length; i ++) d[i] = Integer.parseInt(s[i]);
} catch (Exception e) {
d = new int[h.length];
for (i = 0; i < d.length; i ++) d[i] = h[i];
};

h = new int[d.length];

for (i = 0; i < d.length; i ++) {
h[i] = d[i];
Child = i;
Parent = (Child - 1) / 2;
while ((Child > 0) && ((h[Child] < h[Parent]))) {
j = h[Child];
h[Child] = h[Parent];
h[Parent] = j;
Child = Parent;
Parent = (Child - 1) / 2;
};
};

for (i = 0, k = d.length - 1; i < d.length; i ++, k --) {
d[i] = h[0];
h[0] = h[k];
Parent = 0;
Child = (Parent + 1) * 2;
while (Child <= k) {
if ((Child == k) || (h[Child] > h[Child - 1])) Child --;
if (h[Parent] > h[Child]) {
j = h[Child];
h[Child] = h[Parent];
h[Parent] = j;
};
Parent = Child;
Child = (Parent + 1) * 2;
};
};

for (i = 0; i < d.length; i ++) System.out.println(d[i]);

};

}

回答No.1

fortranxp

ヒープソートとは別名
二分木ソートとも言われ
ております。

参考URL：

http://lecture.ecc.u-tokyo.ac.jp/~cichiji/cp-01/cp-01-10-4.html