※「セキュリティ保護のため...」というメッセージが出る方・日本語が入力できない方へ
(3)ヒープソート

　データを「ヒープ・トリー」という特殊な構造の中に格納し、その構造の
　特殊性を利用してソートしていく。たいへん高速なソートであり、しかも
　メモリーの消費も少ない優秀なソート。

　ヒープソートの最大のメリットは、並べ替える元のデータの品質に関係な
　く、高速にソートできることである。この後に述べる他のソートはデータ
　の元々の並び方によっては極端に遅くなる不幸な場合もある。

　欠点は記述がやや複雑になることか。
　
　【大雑把な処理の手順】
　　　　　　　　42
　　　　　　／　　　＼
　　　　59　　　　　　　97　
　　　／　＼　　　　　／　＼
　　19　　　34　　　63　　　18　
　／　＼　／　＼　／　＼　／　＼
　13　15　28　29　38　60　16　　

HeapTreeというのは、二分木(binary tree)の各節(node)
において、親が必ず二人の子供より大きい、という状態
が保たれているトリーである。

ソート手続きの前半では、このHeapTreeを構築する。そ
うしたら、トップのメンバーと最後のメンバーを入れ替
え、要素数を１つ小さくして、またHeapTreeを構築する。

そのとき、基本的には「壊れた部分」だけを修復すれば
良いので高速に修復ができる。


【Coding Sample】(Heap Sort)

void CSortDlg::HeapSort()
{
	int k;
	long sort_cnt = m_dcnt;
	if (sort_cnt<=1)
		goto loop_e;
	
	//Make Heap, First
	for (k=sort_cnt/2-1; k>=0; k--)
	{
		MakeHeap(k,sort_cnt-1);
	}
	//Here, the biggest member comes to m_data[0]
	for (k=sort_cnt-1; k>=1; k--)
	{
		//Retire top 
		long x = m_data[0];
		m_data[0] = m_data[k];
		m_data[k] = x;

		//Repair Heap
		MakeHeap(0, k-1);
	}
loop_e:
	return;
}

void CSortDlg::MakeHeap(long top, long tmax)
{
	long x;
	long c1,c2;
	c1 = top * 2 + 1;
	c2 = c1 + 1;

	if (c2<=tmax)	//3個比較
	{
		if (m_data[c1]<m_data[c2])	//c2が大きい
		{
			if (m_data[top]<m_data[c2])
			{
				x = m_data[top];
				m_data[top] = m_data[c2];
				m_data[c2] = x;
				MakeHeap(c2,tmax);
			}
		}
		else	//c1が大きい
		{
			if (m_data[top]<m_data[c1])
			{
				x = m_data[top];
				m_data[top] = m_data[c1];
				m_data[c1] = x;
				MakeHeap(c1,tmax);
			}
		}
	}
	else if (c1<=tmax)	//2個比較
	{
		if (m_data[top]<m_data[c1])
		{
			x = m_data[top];
			m_data[top] = m_data[c1];
			m_data[c1] = x;
			MakeHeap(c1,tmax);
		}
	}

}	

【実行時間】(Pentium-75MHz VisualC++5.0 Release Mode)

　　             件数　   乱順　　　　正順　　　　逆順
HeapSort(r)     1000    0.00000     0.00000     0.00000
HeapSort(r)    10000    0.06000     0.05000     0.06000
HeapSort(r)    30000    0.17000     0.11000     0.11000
HeapSort(r)   100000    0.77000     0.55000     0.49000
HeapSort(r)   300000    3.13000     1.64000     1.59000
HeapSort(r)  1000000   13.79000     5.71000     5.82000
HeapSort(r)  3000000   50.31000    17.96000    19.27000

　正順・逆順ともに、乱順より高速になっているのは、順序よく並んでいる
　と、処理がちょうど半分に分割されながら動いてくれるからである。