The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., d-ary heaps were invented by Donald B. Johnson in 1975.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - D-ary heap (en)
- Kopiec a-arny (pl)
- D-арна купа (uk)
|
| rdfs:comment
| - Kopiec a-arny – uogólnienie pojęcia kopca binarnego, drzewo, w którym każdy ojciec posiada synów. Każdy poziom kopca i zawiera ai wierzchołków, z wyjątkiem poziomu ostatniego n, który może mieć od 1 do an wierzchołków. Kopiec taki można zaprezentować w formie tablicy, o rozmiarze 1 + a + a2 + a3 +...+ an-1 + liczba liści. Każdy ze składników tej sumy jest reprezentacją jednego poziomu drzewa. (pl)
- The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., d-ary heaps were invented by Donald B. Johnson in 1975. (en)
- -арна купа або -купа це структура даних, що реалізує чергу з пріоритетом, узагальнення бінарної купи в якій вузли мають дочірніх замість 2. Отже, бінарна купа це 2-купа, а тернарна купа це 3-купа. Ця структура даних дозволяє операції зменшення пріоритету виконуватись швидше ніж у бінарних купах за рахунок повільнішої операції видалення. Такий компроміс приводить до кращої швидкодії деяких алгоритмів, таких як алгоритм Дейкстри, в якому операції зменшення пріоритету відбуваються частіше ніж операції видалення найменшого елемента. Додатково, -арні купи краще взаємодіють з кешем процесора порівняно з бінарною купою, що дозволяє їм на практиці виконуватись швидше всупереч теоретично більшому часу виконання у найгіршому випадку. Подібно до бінарних куп, -арні купи не потребують додаткової пам' (uk)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap. According to Tarjan and Jensen et al., d-ary heaps were invented by Donald B. Johnson in 1975. This data structure allows decrease priority operations to be performed more quickly than binary heaps, at the expense of slower delete minimum operations. This tradeoff leads to better running times for algorithms such as Dijkstra's algorithm in which decrease priority operations are more common than delete min operations. Additionally, d-ary heaps have better memory cache behavior than binary heaps, allowing them to run more quickly in practice despite having a theoretically larger worst-case running time. Like binary heaps, d-ary heaps are an in-place data structure that uses no additional storage beyond that needed to store the array of items in the heap. (en)
- Kopiec a-arny – uogólnienie pojęcia kopca binarnego, drzewo, w którym każdy ojciec posiada synów. Każdy poziom kopca i zawiera ai wierzchołków, z wyjątkiem poziomu ostatniego n, który może mieć od 1 do an wierzchołków. Kopiec taki można zaprezentować w formie tablicy, o rozmiarze 1 + a + a2 + a3 +...+ an-1 + liczba liści. Każdy ze składników tej sumy jest reprezentacją jednego poziomu drzewa. (pl)
- -арна купа або -купа це структура даних, що реалізує чергу з пріоритетом, узагальнення бінарної купи в якій вузли мають дочірніх замість 2. Отже, бінарна купа це 2-купа, а тернарна купа це 3-купа. Ця структура даних дозволяє операції зменшення пріоритету виконуватись швидше ніж у бінарних купах за рахунок повільнішої операції видалення. Такий компроміс приводить до кращої швидкодії деяких алгоритмів, таких як алгоритм Дейкстри, в якому операції зменшення пріоритету відбуваються частіше ніж операції видалення найменшого елемента. Додатково, -арні купи краще взаємодіють з кешем процесора порівняно з бінарною купою, що дозволяє їм на практиці виконуватись швидше всупереч теоретично більшому часу виконання у найгіршому випадку. Подібно до бінарних куп, -арні купи не потребують додаткової пам'яті окрім пам'яті необхідної для збереження масиву елементів купи. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is notable works
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)