基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。 ヒープの概要ヒープの表現ヒープの構築ヒープの計算量ヒープの実装ヒープソート1. ヒープの概要ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要
![ヒープについてわかりやすく解説してみた – Yasufumi Taniguchi – Medium](https://cdn-ak-scissors.b.st-hatena.com/image/square/88c66c11b3111e5634561be0a85028d41e22cd66/height=288;version=1;width=512/https%3A%2F%2Fmiro.medium.com%2Fv2%2Fresize%3Afit%3A668%2F1%2Ads0JXOw3lLqNo6hw__NtZw.png)