File:Sorting_heapsort_anim.gif · Wikimedia Commons · See Wikimedia Commons
ヒープソート
Sign in to saveIn computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that heap, placing it at the end of the array in a similar manner to Selection sort.
In the Vinony graph
Vinony's link graph records 98 inbound references to ヒープソート, and connects out to sorting algorithm, CPU cache and tree sort.
Vinony files it under Comparison sorts and Heaps (data structures).
Vinony links it to 38 Wikipedia language editions.
Key facts
- Algorithm.caption
- A run of heapsort sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.
- Algorithm.data
- Array
- Algorithm.time
- O(n\log n)
- Algorithm.average time
- O(n\log n)
- Algorithm.best time
- O(n\log n) (distinct keys)or O(n) (equal keys)
- Algorithm.space
- O(n) total O(1) auxiliary
- Algorithm.class
- Sorting algorithm
- Algorithm.image
- File:Sorting heapsort anim.gif
via Wikipedia infobox
Wikidata facts
- Instance of
- comparison sort
- Image
- Binary heap bottomup vs topdown.svg
Show 5 more facts
- maintained by WikiProject
- WikiProject Mathematics
- derivative work
- smoothsort
- time of discovery or invention
- 1964-00-00
- Commons category
- Heap sort
Sources (2)
via Wikidata · CC0
Article · 日本語
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである（ヒープ領域とは無関係であることに注意する）。 アルゴリズムは、以下のように2つの段階から構成される。 1. * 未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。 2. * ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。 計算量は O となる。安定ソートではない。
Abstract from DBpedia / Wikipedia · CC BY-SA