ヒープについてわかりやすく解説してみた – Yasufumi Taniguchi – Medium

基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。 ヒープの概要ヒープの表現ヒープの構築ヒープの計算量ヒープの実装ヒープソート1. ヒープの概要ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要

[fog-og-frog2]

↓ https://stackoverflow.com/questions/660855/what-is-the-origin-of-the-term-heap-for-the-free-store　C言語のルーツであるALGOL 68の予約語にあるけどフリーストアを意味する言葉として適当に名づけたんじゃね？、だそうです...

[sgo2]

id:UhoNiceGuy https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E9%A0%98%E5%9F%9F "ヒープ (heap) とは、『山積み』という言葉の中の『山』をさす英単語である。" なので直接は関係無い

[onigra]

“ヒープは木構造の1つで、二分木として表現されます。木構造はポインタや配列を使って実装されます。この記事では下に示すように、配列による実装を用います。配列を用いた実装は空間計算量の観点で、ポインタを用

[hirorinya]

学び

[opnihc]

昔アルゴリズム本読みながらコード書いたときに感動したの思い出したわ

[yarumato]

“基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介”

[nakamako13]

後で読む 記事内の講義についても確認してみよう

[c-matt]

一瞬自分もスタックとヒープのヒープかと思った。紛らわしいよね。で、まさか関係ないとは！！！

[civic800]

子供のプログラミング授業の課題を見てて最近やったばかりなのでメモしとく

[UhoNiceGuy]

この、priority queueのデータ構造と所謂mallocで確保するメモリ領域が同じheapという名称になった歴史を誰か解説してくれるとありがたい。相変わらずの他力本願

[hase0510]

Pythonはheapq、C++はstd::priority_queue、Javaはjava.util.PriorityQueue<E>、C#はSystem.Collections.Generic.PriorityQueue<TElement,TPriority>、Rustはstd::collections::binary_heap

[sakaiwa]

“min_heapify(array, 2)によってインデックス2のノードとインデックス4”