Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Weak heap
Résumé
In computer science, a weak heap is a data structure for priority queues, combining features of the binary heap and binomial heap. It can be stored in an array as an implicit binary tree like a binary heap, and has the efficiency guarantees of binomial heaps.
A sorting algorithm using weak heaps, weak-heapsort, uses a number of comparisons that is close to the theoretical lower bound on the number of comparisons required to sort a list, so is particularly useful when comparison is expensive, such as when comparing strings using the full Unicode collation algorithm.
A weak heap is most easily understood as a heap-ordered multi-way tree stored as a binary tree using the "right-child left-sibling" convention. (This is equivalent to, but reversed from, the usual left-child right-sibling binary tree.)
In the multi-way tree, and assuming a max-heap, each parent's key is greater than or equal to (≥) all the child keys (and thus, by induction, all members of the subtree).
Expressed as a binary tree, this translates to the following invariants:
The root node has no left child
For every node, the value associated with that node is greater than or equal to the values associated with all nodes in its right subtree.
The leaves of the tree have heights that are all within one of each other.
The last condition is a consequence of the fact that an implicit binary tree is a complete binary tree.
The structure of this tree maps very neatly onto the traditional 1-based (Ahnentafel) implicit binary tree arrangement, where node k has a next sibling (left child) numbered 2k and a first child (right child) numbered 2k + 1, by adding an additional root numbered 0. This root has no siblings, only a first child, which is node 1 (2×0 + 1).
This structure is very similar to that of a binomial heap, with a tree of height h being composed of a root plus trees of heights h − 1, h − 2, ..., 1. A perfect (no missing leaves) weak heap with 2n elements is exactly isomorphic to a binomial heap of the same size, but the two algorithms handle sizes which are not a power of 2 differently: a binomial heap uses multiple perfect trees, while a weak heap uses a single imperfect tree.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.