ヒープソートの復習.

Slides:



Advertisements
Similar presentations
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
Advertisements

4.3 マージソート.
4.ソート問題とアルゴリズム 4-1.ソート問題について 4-2.簡単なソートアルゴリズム 4-3.高度なソートアルゴリズム
離散システム特論 整列(sorting)アルゴリズム 2.
ヒープソートの演習 第13回.
第12回 ソート(3): シェルソート、クイックソート
アルゴリズムとデータ構造1 2008年7月22日
アルゴリズムとデータ構造 第8回 ソート(3).
第10回 整列 ~ バブルソート,挿入ソート,選択ソート~
第11回 整列 ~ シェルソート,クイックソート ~
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
第8講: 平成19年11月9日 (金) 4限 E252教室 探索アルゴリズム(1).
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
On the Enumeration of Colored Trees
Problem G : Entangled Tree
アルゴリズムとデータ構造 第6回演習解答 2015/11/18実施 アルゴリズムとデータ構造 2015.
4.整列のアルゴリズム.
第10回 ソート(1):単純なソートアルゴリズム
2009/11/20 探索アルゴリズム(2) 第8講: 平成21年11月20日 (金) 4限 E252教室 コンピュータアルゴリズム.
探索アルゴリズム (1) 第7講: 平成21年11月13日 (金) 4限 E252教室.
データ構造とアルゴリズム 分割統治 ~ マージソート~.
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
エージェントを管理するボスの苦悩 問題 n人のエージェントを部下に持つボスがいる. エージェントは出張・帰還を頻繁に繰り返す.
アルゴリズムとデータ構造 第7回探索のためのデータ構造(1) 2015/11/18 アルゴリズムとデータ構造 2015.
第11回 整列 ~ シェルソート,クイックソート ~
二分探索木によるサーチ.
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
算法数理工学 第3回 定兼 邦彦.
“Purely Functional Data Structures” セミナー
アルゴリズムとデータ構造1 2005年7月26日
アルゴリズムとデータ構造1 2006年6月16日
情報工学概論 (アルゴリズムとデータ構造)
ソートアルゴリズムの種類 選択ソート (selection sort) バブルソート (bubble sort)
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
第9回 優先度つき待ち行列,ヒープ,二分探索木
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
A Simple Algorithm for Generating Unordered Rooted Trees
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとプログラミング (Algorithms and Programming)
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング 4 整列アルゴリズム.
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング 4 木構造とヒープ.
プログラミング 3 スタックとキュー.
15.cons と種々のデータ構造.
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
情報知能学科「アルゴリズムとデータ構造」
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
D: 壊れかけのヒープ 問題案: 稲葉.
第9回 優先度つき待ち行列,ヒープ,二分探索木
ハフマン符号長の効率的な求め方.
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2011年6月16日
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
ヒープソートの復習 第12回.
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
平面走査法を使った 一般線分の 交点列挙アルゴリズム
ヒープソート.
ヒープソート.
アルゴリズムとデータ構造 2013年6月20日
参考:大きい要素の処理.
データ構造と アルゴリズムI 第三回 知能情報学部 新田直也.
Presentation transcript:

ヒープソートの復習

ヒープソート(heap sort)(p.94) ※ ヒープを用いてデータの整列を行うアルゴリズム 計算量 O (n log n) ヒープ : 配列により半順序木を実現したもの 常に子が親より 大きい木の例 常に子が親より 小さい木の例 3 10 5 9 8 9 6 8 9 10 6 3 7 6 10 18 9 4 1 2

ヒープソートの原理 ※ リストL 2,9,5,6,… 1.ヒープ(半順序木)を作る(優先度つき待ち行列に入れる) 2.以下の処理を繰り返して並べかえる ヒープの先頭の要素と末尾の要素を交換 [先頭]~[末尾-1]の部分の半順序を回復させる 優先度つき 待ち行列 リストL 2,9,5,6,… 9 6 5 2

1.ヒープを作る 部分木の根の要素を適切な位置まで下げる操作を繰り返すことで,半順序木をボトムアップに構築する 10 6 9 5 15 15 ← a[0] 要素数 n = 15 6 9 5 15 15 12 ← a[n/2-1] (=a[6]) 3 18 9 8 11 9 20 10 ← a[n-1] (=a[14])

2.並べかえ 2-1 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12 2-1 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12 15 11 3 20 [0] [n-1] a 12 5 9 6 8 9 10 10 18 9 15 11 15 20 3

着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある 2.並べかえ(つづき) この部分の 半順序を 回復させる 2-1 残りの部分の半順序の回復 10 5 6 8 9 18 12 15 11 3 20 子が親より小さい間, 2つの子のうち 小さい方の子 と親を交換していく この部分のヒープを再構成 [0] [1] [2] [3] [4] [7] [8] [n-2] [n-1] a 12 5 9 6 8 9 10 10 18 9 15 11 15 20 5 12 6 10 3 着目する節点の左の子は2*i+1、右の子はそのひとつ後ろにある

プログラムの概要 1.ヒープ(半順序木)を作る 2.以下の処理を繰り返す begin heapsort ヒープの先頭の要素と末尾の要素を交換 トップダウンに[先頭]~[末尾-1]の部分の半順序を回復させる heapsort heapify downMin deleteMin downMin end