Statements (26)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:architecture
|
| gptkbp:compatibleWith |
binary search tree
balanced binary search tree |
| gptkbp:hasProperty |
parent node is greater than or equal to children (max-heap)
parent node is less than or equal to children (min-heap) |
| gptkbp:hasVariant |
min-heap
max-heap |
| https://www.w3.org/2000/01/rdf-schema#label |
binary heap
|
| gptkbp:implementedIn |
array
|
| gptkbp:introduced |
gptkb:J._W._J._Williams
1964 |
| gptkbp:supports |
insert
extract-max heapify extract-min |
| gptkbp:time_complexity_(extract) |
O(log n)
|
| gptkbp:time_complexity_(find-min_or_find-max) |
O(1)
|
| gptkbp:time_complexity_(insert) |
O(log n)
|
| gptkbp:type |
heap
complete binary tree |
| gptkbp:used_in_algorithm |
gptkb:Prim's_algorithm
gptkb:Dijkstra's_algorithm gptkb:Heapsort |
| gptkbp:usedFor |
priority queue implementation
|
| gptkbp:bfsParent |
gptkb:PriorityQueue
|
| gptkbp:bfsLayer |
6
|