2879:: First, a new node with a key and a priority is created. In addition, the node is assigned a number of levels, which dictates the size of the array of pointers. Then a search is performed to find the correct position where to insert the new node. The search starts from the first node and from the highest level. Then the skip list is traversed down to the lowest level until the correct position is found. During the search, for every level the last traversed node will be saved as parent node for the new node at that level. In addition, the node to which the pointer, at that level, of the parent node points towards, will be saved as the successor node of the new node at that level. Afterwards, for every level of the new node, the pointers of the parent node will be set to the new node. Finally, the pointers, for every level, of the new node will be set to the corresponding successor nodes.
2655:) algorithm computes a dynamically changing triangulation of a terrain. It works by splitting triangles where more detail is needed and merging them where less detail is needed. The algorithm assigns each triangle in the terrain a priority, usually related to the error decrease if that triangle would be split. The algorithm uses two priority queues, one for triangles that can be split and another for triangles that can be merged. In each step the triangle from the split queue with the highest priority is split, or the triangle from the merge queue with the lowest priority is merged with its neighbours.
2362:. However, it does not specify how two elements with same priority should be served, and indeed, common implementations will not return them according to their order in the queue. It implements a max-priority-queue, and has three parameters: a comparison object for sorting such as a function object (defaults to less<T> if unspecified), the underlying container for storing the data structures (defaults to std::vector<T>), and two iterators to the beginning and end of a sequence. Unlike actual STL containers, it does not allow
2837:
3220:
591:(1) in all tree and heap implementations by caching the highest priority element after every insertion and removal. For insertion, this adds at most a constant cost, since the newly inserted element is compared only to the previously cached minimum element. For deletion, this at most adds an additional "peek" cost, which is typically cheaper than the deletion cost, so overall time complexity is not significantly impacted.
3234:
operation assigns the elements uniformly random to the processors which insert the elements into their local queues. Note that single elements can still be inserted into the queue. Using this strategy the global smallest elements are in the union of the local smallest elements of every processor with
2897:
If the concurrent access to a priority queue is allowed, conflicts may arise between two processes. For example, a conflict arises if one process is trying to insert a new node, but at the same time another process is about to delete the predecessor of that node. There is a risk that the new node is
2588:
If instead, a graph is stored as node objects, and priority-node pairs are inserted into a heap, altering the priority of a particular vertex is not necessary if one tracks visited nodes. Once a node is visited, if it comes up in the heap again (having had a lower priority number associated with it
43:
In a priority queue, elements with high priority are served before elements with low priority. In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is
2478:
connection) is forwarded with the least delay and the least likelihood of being rejected due to a queue reaching its maximum capacity. All other traffic can be handled when the highest priority queue is empty. Another approach used is to send disproportionately more traffic from higher priority
2832:
If the priority queue allows concurrent access, multiple processes can perform operations concurrently on that priority queue. However, this raises two issues. First of all, the definition of the semantics of the individual operations is no longer obvious. For example, if two processes want to
195:
can be implemented as particular kinds of priority queues, with the priority determined by the order in which the elements are inserted. In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved. In a queue, the
3560:
By removing several elements at once a considerable speedup can be reached. But not all algorithms can use this kind of priority queue. Dijkstra's algorithm for example can not work on several nodes at once. The algorithm takes the node with the smallest distance from the priority queue and
2833:
extract the element with the highest priority, should they get the same element or different ones? This restricts parallelism on the level of the program using the priority queue. In addition, because multiple processes have access to the same element, this leads to contention.
2536:
Usually a limitation (policer) is set to limit the bandwidth that traffic from the highest priority queue can take, in order to prevent high priority packets from choking off all other traffic. This limit is usually never reached due to high level control instances such as the
3215:
The rest of this section discusses a queue-based algorithm on distributed memory. We assume each processor has its own local memory and a local (sequential) priority queue. The elements of the global (parallel) priority queue are distributed across all processors.
597:
are specialized queues that are optimized for the case where no item is ever inserted that has a lower priority (in the case of min-heap) than any item previously extracted. This restriction is met by several practical applications of priority queues.
2635:) is used to keep track of unexplored routes; the one for which the estimate (a lower bound in the case of A*) of the total path length is smallest is given highest priority. If memory limitations make best-first search impractical, variants like the
2779:
cost, and there is no practical gain to parallelize such an operation. One possible change is to allow the concurrent access of multiple processors to the same priority queue. The second possible change is to allow batch operations that work on
1657:
of priority queues naturally suggest a sorting method: insert all the elements to be sorted into a priority queue, and sequentially remove them; they will come out in sorted order. This is actually the procedure used by several
185:, inspecting the first few highest- or lowest-priority elements, clearing the queue, clearing subsets of the queue, performing a batch insert, merging two or more queues into one, incrementing priority of any element, etc.
3212:, which first deletes the elements and then inserts them back with the updated keys. All these operations are highly parallel, and the theoretical and practical efficiency can be found in related research papers.
2469:
queuing due to insufficient bandwidth, all other queues can be halted to send the traffic from the highest priority queue upon arrival. This ensures that the prioritized traffic (such as real-time traffic, e.g. an
236:() { highest = list.get_first_element() foreach node in list { if highest.priority < node.priority { highest = node } } list.remove(highest) return highest }
2556:. The events are added to the queue with their simulation time used as the priority. The execution of the simulation proceeds by repeatedly pulling the top of the queue and executing the event thereon.
3198:
2715:
Parallelization can be used to speed up priority queues, but requires some changes to the priority queue interface. The reason for such changes is that a sequential update usually only has
1615:
360:
that either supply additional operations or outperform heap-based implementations for specific types of keys, specifically integer keys. Suppose the set of possible keys is {1, 2, ..., C}.
3102:
2366:
of its elements (it strictly adheres to its abstract data type definition). STL also has utility functions for manipulating another random-access container as a binary max-heap. The
3528:
2840:
Node 3 is inserted and sets the pointer of node 2 to node 3. Immediately after that, node 2 is deleted and the pointer of node 1 is set to node 4. Now node 3 is no longer reachable.
3475:
1557:
577:
1628:
Brodal queues and strict
Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a
3262:
elements of each local queue are removed and collected in a result set. The elements in the result set are still associated with their original processor. The number of elements
253:(node) { foreach (index, element) in list { if node.priority < element.priority { list.insert_at_index(node,index) break } } }
330:) time; this is typical where one might already have access to these data structures, such as with third-party or standard libraries. From a space-complexity standpoint, using
2844:
The concurrent access to a priority queue can be implemented on a
Concurrent Read, Concurrent Write (CRCW) PRAM model. In the following the priority queue is implemented as a
579:
time. However it is stated by the author that, "Our algorithms have theoretical interest only; The constant factors involved in the execution times preclude practicality."
4797:
2213:
2177:
2141:
1906:
1870:
1803:
1767:
1731:
4537:
3013:
2777:
2093:
2065:
2003:
1975:
1947:
209:
There are a variety of simple, usually inefficient, ways to implement a priority queue. They provide an analogy to help one understand what a priority queue is.
2742:
2037:
1834:
3599:
3579:
3548:
3420:
3400:
3380:
3360:
3340:
3320:
3300:
3280:
3260:
3033:
2955:
2931:
2822:
2798:
2438:
3892:
1180:
4256:
4127:
4032:
3553:
The priority queue can be further improved by not moving the remaining elements of the result set directly back into the local queues after a
2541:
216:(1) insertion time). Whenever the highest-priority element is requested, search through all elements for the one with the highest priority. (
5166:
167:), which returns the highest-priority element but does not modify the queue, is very frequently implemented, and nearly always executes in
4523:"In order to implement Prim's algorithm efficiently, we need a fast way to select a new edge to add to the tree formed by the edges in A."
4452:
4476:
2872:
mark marks if the node is about to be deleted by a process. This ensures that other processes can react to the deletion appropriately.
2683:, one can achieve a good running time. This min heap priority queue uses the min heap data structure which supports operations such as
2396:
4842:
4808:
2899:
124:
Some conventions reverse the order of priorities, considering lower values to be higher priority, so this may also be known as "
3107:
196:
priority of each inserted element is monotonically decreasing; thus, the first element inserted is always the first retrieved.
3422:
elements can be returned. All other elements of the result set are inserted back into their local queues. The running time of
5136:
4715:
4657:
4632:
Symposium on
Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016)
4332:
3875:
3699:
2229:
We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to
2385:
3226:
is executed on a priority queue with three processors. The green elements are returned and removed from the priority queue.
4533:
1506:). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.
243:(n) insertion sort time), whenever the highest-priority element is requested, the first one in the list can be returned. (
2585:, although one also needs the ability to alter the priority of a particular vertex in the priority queue efficiently.
5075:
4769:
4516:
4389:
4186:
4100:
4016:
3773:
3666:
2406:
2104:
331:
307:
4248:
1562:
3691:
1666:
provided by the priority queue is removed. This sorting method is equivalent to the following sorting algorithms:
4865:
2893:
mark is than set to true for that node. Finally the pointers of the parent nodes of the deleted node are updated.
607:
2289:, then one can use the given procedure to create a priority queue where pulling the highest-priority element is
341:
From a computational-complexity standpoint, priority queues are congruent to sorting algorithms. The section on
4870:
4163:. FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183.
3925:
3557:
operation. This saves moving elements back and forth all the time between the result set and the local queues.
2861:
2334:
1663:
614:
indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "
4835:
4944:
3382:
elements are again removed from each local queue and put into the result set. This is done until the global
3050:
5205:
3480:
2475:
2471:
2402:
1518:
527:
3429:
4949:
4932:
2640:
2380:
4036:
3043:
of the original priority queue and the batch of insertions. If the batch is already sorted by the key,
5148:
4915:
4910:
4759:
4506:
3763:
3656:
2969:
2961:
587:" operations for every "extract-min" operation, the time complexity for peek actions can be reduced to
584:
192:
188:
155:
93:
36:
32:
4905:
3976:
Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues",
3807:
2553:
2412:
2341:
1629:
1455:
52:
4315:
4270:
4119:
4083:
3912:
434:
time in the worst case. These queues are useful for sorting the vertices of a graph by their degree.
5200:
4939:
4898:
4828:
4580:
4169:
3821:
2526:
4348:
4293:
3601:
nodes. So using k-element operations destroys the label setting property of
Dijkstra's algorithm.
259:() { highest = list.get_at_index(list.length-1) list.remove(highest) return highest }
5179:
5156:
2853:
2582:
2367:
2353:
594:
493:
is the number of bits in the priority value. The space can be reduced significantly with hashing.
4805:
is a generic priority queue (heap) implementation (in C) used by the Apache HTTP Server project.
4682:
Proceedings of the 23rd ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming
3235:
high probability. Thus each processor holds a representative part of the global priority queue.
5161:
4961:
4630:
Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for
Parallel Ordered Sets",
4575:
4445:
4310:
4265:
4164:
4078:
3907:
3816:
3342:
smallest elements of the result set are determined. With high probability these are the global
2563:
2359:
2225:
A sorting algorithm can also be used to implement a priority queue. Specifically, Thorup says:
51:, they are conceptually distinct from heaps. A priority queue is an abstract data type like a
4612:
2544:, which can be programmed to inhibit calls which would exceed the programmed bandwidth limit.
2183:
2147:
2111:
1876:
1840:
1773:
1737:
1701:
67:, a priority queue can be implemented with a heap or another method such as an ordered array.
5087:
5042:
5004:
4814:
3802:
2704:
2672:
2620:
2455:
2356:
2349:
1694:
1654:
1294:
354:
288:
268:
89:
48:
4785:
5027:
4747:
4494:
4309:. Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184.
3755:
3644:
2983:
2857:
2747:
2601:
2487:
2423:
2071:
2043:
1981:
1953:
1925:
64:
2427:
345:, below, describes how efficient sorting algorithms can create efficient priority queues.
8:
4373:
2965:
2668:
2624:
2616:
2538:
2499:
4680:
Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018), "PAM: parallel augmented maps",
5070:
5055:
4920:
4880:
4721:
4663:
4635:
4593:
4427:
4410:
4068:
2581:
or matrix, priority queue can be used to extract minimum efficiently when implementing
2530:
2522:
2511:
2483:
2462:
2022:
1819:
929:
438:
28:
4155:
4067:, Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77,
2718:
2600:
requires one to repeatedly obtain the two lowest-frequency trees. A priority queue is
4989:
4888:
4765:
4725:
4711:
4653:
4512:
4470:
4385:
4328:
4182:
4096:
4012:
3921:
3871:
3834:
3769:
3695:
3662:
2612:
1659:
56:
4597:
4431:
5012:
4743:
4703:
4667:
4645:
4585:
4490:
4419:
4377:
4320:
4275:
4222:
4174:
4136:
4088:
3985:
3917:
3863:
3826:
3751:
3640:
3584:
3564:
3533:
3405:
3385:
3365:
3345:
3325:
3305:
3285:
3265:
3245:
3018:
2940:
2916:
2849:
2807:
2783:
2707:. Lower the weight, higher the priority and higher the weight, lower the priority.
2680:
2459:
20:
3730:
and Dan E. Willard. Surpassing the information theoretic bound with fusion trees.
2631:, trying out the most promising routes first. A priority queue (also known as the
5032:
4974:
4698:
Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019).
4240:
4115:
3727:
3714:
P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In
2836:
2676:
2567:
2434:
2015:
1918:
501:
357:
4207:
4059:
3200:. Other operations for priority queue can be applied similarly. For instance,
338:
takes more storage, since it requires to store extra references to other nodes.
5124:
5102:
4851:
4755:
4589:
4502:
4352:
4301:
3794:
3652:
2700:
2628:
2597:
2578:
2009:
1912:
1237:
631:
300:
181:
More advanced implementations may support more complicated operations, such as
168:
4707:
3990:
1432:) time (where both complexities can be amortized). Another algorithm achieves
5194:
5097:
4994:
4979:
4563:
4405:
4297:
4244:
4203:
4004:
3855:
3838:
3798:
3683:
3620:
3615:
2913:
In this setting, operations on a priority queue is generalized to a batch of
2419:
module, which implements a min-heap on top of any compatible data structure.
2374:
867:
4649:
4423:
4324:
4249:"Fibonacci heaps and their uses in improved network optimization algorithms"
4092:
3867:
2498:) experience lower latency than other applications which can be served with
4613:"A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention"
3716:
Proceedings of the 16th Annual
Symposium on Foundations of Computer Science
3581:
nodes, working at one node could change the distance of another one of the
3561:
calculates new distances for all its neighbor nodes. If you would take out
2856:-free. The nodes of the skip list consists of a unique key, a priority, an
2503:
1345:
1119:
988:
804:
377:
296:
4700:
Sequential and
Parallel Algorithms and Data Structures - The Basic Toolbox
4140:
342:
318:) time, although building trees from existing sequences of elements takes
239:
In another case, one can keep all the elements in a priority sorted list (
5092:
5017:
4178:
4055:
3610:
2664:
2507:
2416:
663:
505:
497:
384:
335:
60:
4564:"Fast and lock-free concurrent priority queues for multi-thread systems"
4279:
1643:
5080:
4984:
4751:
4498:
3949:
3759:
3648:
3104:
cost. Otherwise, we need to first sort the batch, so the cost will be
2964:, the parallel priority queue can be easily implemented using parallel
1809:
39:
abstract data type. Each element in a priority queue has an associated
4697:
4226:
5022:
4969:
2845:
2286:
2220:
2099:
1049:
726:
3830:
178:(1) performance is crucial to many applications of priority queues.
5119:
5065:
4893:
4640:
2490:(MAC) sub-layer to ensure that high-priority applications (such as
2363:
1689:
4820:
4802:
4073:
2885:: First, the skip list is traversed until a node is reached whose
5114:
5060:
3219:
2466:
2454:
Priority queuing can be used to manage limited resources such as
267:
To improve performance, priority queues are typically based on a
212:
For instance, one can keep all the elements in an unsorted list (
75:
A priority queue must at least support the following operations:
4815:
UC Berkeley - Computer
Science 61B - Lecture 24: Priority Queues
4793:
4120:"On the Efficiency of Pairing Heaps and Related Data Structures"
2293:(1) time, and inserting new elements (and deleting elements) is
423:
if needed until it again points to a non-empty list; this takes
5109:
5050:
2389:
class, which implements a min-priority-queue as a binary heap.
3893:"Average Case Analysis of Heap Building by Repeated Insertion"
2399:
class, which implements an array-backed, quaternary min-heap.
4764:(2nd ed.). MIT Press and McGraw-Hill. pp. 138–142.
3661:(2nd ed.). MIT Press and McGraw-Hill. pp. 476–497.
2658:
2552:
Another use of a priority queue is to manage the events in a
2515:
2345:
2957:
smallest elements of the priority queue and returns those.
295:
elements. Variants of the basic heap data structure such as
5131:
4817:(video) - introduction to priority queues using binary heap
4408:(2007). "Equivalence between priority queues and sorting".
3884:
2652:
2636:
2518:
2495:
2491:
2392:
2269:
That is, if there is a sorting algorithm which can sort in
4742:
4489:
4360:
Proc. 7th Annual ACM-SIAM Symposium on
Discrete Algorithms
3639:
3193:{\textstyle O(k\log(1+{\frac {n}{k}})+k\log k)=O(k\log n)}
2241:) time per key, then there is a priority queue supporting
2898:
added to the skip list, yet it is not longer reachable. (
343:
the equivalence of priority queues and sorting algorithms
4511:(3rd ed.). MIT Press and McGraw-Hill. p. 634.
3633:
4702:. Springer International Publishing. pp. 226–229.
4292:
2313:) sort algorithm, one can create a priority queue with
1632:
data structure achieving the same optimum, except that
1408:
is the operation of building a heap from a sequence of
485:) time, but has a space cost for small queues of about
3587:
3567:
3536:
3483:
3432:
3408:
3388:
3368:
3348:
3328:
3308:
3288:
3268:
3248:
3110:
3053:
3021:
2986:
2943:
2919:
2810:
2786:
2750:
2721:
2377:
module implements a binary min-heap on top of a list.
415:
deletes and returns one item from the list with index
3789:
3787:
3785:
3750:
2186:
2150:
2114:
2074:
2046:
2025:
1984:
1956:
1928:
1879:
1843:
1822:
1776:
1740:
1704:
1644:
Equivalence of priority queues and sorting algorithms
1565:
1521:
530:
4679:
4629:
2848:. In addition, an atomic synchronization primitive,
2800:
elements, instead of just one element. For example,
4061:
Proc. 7th Scandinavian Workshop on Algorithm Theory
4058:(2000), "Improved upper bounds for pairing heaps",
3950:"Binomial Heap | Brilliant Math & Science Wiki"
3402:smallest elements are in the result set. Now these
2703:of the edges is used to decide the priority of the
2486:also include the concept of priority queues at the
4257:Journal of the Association for Computing Machinery
4233:
4128:Journal of the Association for Computing Machinery
3782:
3593:
3573:
3542:
3522:
3469:
3414:
3394:
3374:
3354:
3334:
3314:
3294:
3274:
3254:
3192:
3096:
3027:
3007:
2949:
2925:
2816:
2792:
2771:
2736:
2221:Using a sorting algorithm to make a priority queue
2207:
2171:
2135:
2087:
2059:
2031:
1997:
1969:
1941:
1900:
1864:
1828:
1797:
1761:
1725:
1609:
1551:
1509:
610:of various heap data structures. The abbreviation
571:
47:While priority queues are often implemented using
4201:
3971:
3969:
3282:that is removed from each local queue depends on
2370:also have an implementation in the library heap.
1648:
1450:
1448:
1446:
102:: remove the element from the queue that has the
5192:
4372:
3890:
3850:
3848:
1462:), a generic transformation reduces the cost of
376:are needed and in case of integer priorities, a
4610:
2646:
2607:
303:can provide better bounds for some operations.
143:" functions, which can be combined to produce "
4380:(2004). "7.3.6. Bottom-Up Heap Construction".
3966:
2409:class, which implements a max-priority-queue.
2333:A priority queue is often considered to be a "
1610:{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}
1443:
4836:
4693:
4691:
4568:Journal of Parallel and Distributed Computing
4561:
4239:
3975:
3845:
3793:
2827:
2547:
1265:
1256:
1208:
1199:
1151:
1138:
1112:
1099:
1090:
1081:
1068:
1022:
1007:
902:
797:
784:
771:
758:
745:
611:
279:) performance for inserts and removals, and
4557:
4555:
4108:
3768:(1st ed.). MIT Press and McGraw-Hill.
3718:, pages 75-84. IEEE Computer Society, 1975.
601:
135:This may instead be specified as separate "
59:; just as a list can be implemented with a
4843:
4829:
4688:
4623:
4562:Sundell, Håkan; Tsigas, Philippas (2005).
2864:, for each level, to the next nodes and a
2710:
2659:Prim's algorithm for minimum spanning tree
1624:
1622:
82:: check whether the queue has no elements.
4809:Survey of known priority queue structures
4758:(2001) . "Section 6.5: Priority queues".
4639:
4579:
4314:
4269:
4168:
4157:Towards a Final Analysis of Pairing Heaps
4082:
4072:
3989:
3911:
3820:
3015:cost and yields a tree that contains the
2651:The Real-time Optimally Adapting Meshes (
634:. Names of operations assume a min-heap.
310:is used, insertion and removal also take
4552:
4007:(1998). "10.2. Structural Abstraction".
3891:Hayward, Ryan; McDiarmid, Colin (1991).
3655:(2001) . "Chapter 20: Fibonacci Heaps".
3218:
2835:
2643:to allow removal of low-priority items.
2589:earlier), it is popped-off and ignored.
2577:When the graph is stored in the form of
2441:structure, which implements a min-heap.
204:
4114:
4031:
4003:
3732:Journal of Computer and System Sciences
3097:{\textstyle O(k\log(1+{\frac {n}{k}}))}
2905:
2572:
2449:
1619:
262:
5193:
4475:: CS1 maint: archived copy as title (
4404:
4382:Data Structures and Algorithms in Java
4353:"Worst-Case Efficient Priority Queues"
4347:
4153:
4054:
4048:
3860:Data Structures and Network Algorithms
3854:
3746:
3744:
3742:
3740:
3682:
3523:{\textstyle k=\Omega (p\cdot \log(p))}
2639:algorithm can be used instead, with a
16:Abstract data type in computer science
4824:
4540:from the original on 9 September 2014
4526:
4202:Haeupler, Bernhard; Sen, Siddhartha;
3470:{\textstyle O({\frac {k}{p}}\log(n))}
2619:, find the shortest path between two
1552:{\displaystyle \Omega (\log \log n),}
1412:unsorted elements. It can be done in
572:{\displaystyle O(\log n/\log \log C)}
4536:. Geek for Geeks. 18 November 2012.
2824:elements with the highest priority.
1490:(1) time (amortized, if the cost of
348:
4850:
4673:
4483:
3737:
3550:is the size of the priority queue.
2980:on the binary search tree that has
2301:) time. For example, if one has an
13:
4736:
4384:(3rd ed.). pp. 338–341.
4011:(1st ed.). pp. 158–162.
3490:
1522:
380:can be constructed as an array of
14:
5217:
4779:
4009:Purely Functional Data Structures
3978:Journal of Functional Programming
2592:
2105:Self-balancing binary search tree
332:self-balancing binary search tree
308:self-balancing binary search tree
230:(node) { list.append(node) }
199:
2852:, is used to make the skip list
137:peek_at_highest_priority_element
128:", and is often referred to as "
4604:
4458:from the original on 2011-07-20
4438:
4398:
4366:
4341:
4286:
4195:
4147:
4025:
3997:
3942:
3692:Springer Science+Business Media
2444:
1474:is the sum of the old costs of
583:For applications that do many "
3858:(1983). "3.3. Leftist heaps".
3721:
3708:
3676:
3517:
3514:
3508:
3493:
3464:
3461:
3455:
3436:
3204:can be done by first applying
3187:
3172:
3163:
3145:
3126:
3114:
3091:
3088:
3069:
3057:
3002:
2990:
2766:
2754:
2731:
2725:
2699:. In this implementation, the
2458:on a transmission line from a
2202:
2196:
2166:
2160:
2130:
2124:
1895:
1889:
1859:
1853:
1792:
1786:
1756:
1750:
1720:
1714:
1649:Using a priority queue to sort
1601:
1569:
1543:
1525:
1399:
566:
534:
353:There are several specialized
159:(in this context often called
1:
3626:
3322:. By parallel selection the
3302:and the number of processors
3242:is executed, as the smallest
2426:extension contains the class
1675:Priority Queue Implementation
395:. Inserting an item with key
174:time. This operation and its
145:pull_highest_priority_element
100:pull_highest_priority_element
70:
3922:10.1016/0196-6774(91)90027-v
2647:ROAM triangulation algorithm
2608:Best-first search algorithms
2525:using existing home wiring (
2328:
2097:
2007:
1910:
1807:
1687:
183:pull_lowest_priority_element
96:with an associated priority.
7:
5167:Directed acyclic word graph
4933:Double-ended priority queue
3688:The Algorithm Design Manual
3604:
3362:smallest elements. If not,
3238:This property is used when
2641:double-ended priority queue
2521:(a standard for high-speed
2465:. In the event of outgoing
10:
5222:
4761:Introduction to Algorithms
4590:10.1109/IPDPS.2003.1213189
4508:Introduction to Algorithms
3765:Introduction to Algorithms
3658:Introduction to Algorithms
2970:join-based tree algorithms
2828:Concurrent parallel access
2482:Many modern protocols for
5175:
5147:
5041:
5003:
4960:
4879:
4858:
4708:10.1007/978-3-030-25209-0
4634:, ACM, pp. 253–264,
4617:Technical Report 2018-003
4241:Fredman, Michael Lawrence
4116:Fredman, Michael Lawrence
3991:10.1017/s095679680000201x
3808:SIAM Journal on Computing
2554:discrete event simulation
2548:Discrete event simulation
2348:1998 standard, specifies
2342:Standard Template Library
411:, both in constant time.
4899:Retrieval Data Structure
4611:Lindén, Jonsson (2013),
2933:elements. For instance,
2602:one method of doing this
2335:container data structure
2208:{\displaystyle n\log(n)}
2172:{\displaystyle n\log(n)}
2136:{\displaystyle n\log(n)}
1901:{\displaystyle n\log(n)}
1865:{\displaystyle n\log(n)}
1798:{\displaystyle n\log(n)}
1762:{\displaystyle n\log(n)}
1726:{\displaystyle n\log(n)}
1470:, while the new cost of
602:Summary of running times
595:Monotone priority queues
399:appends the item to the
291:initially from a set of
5180:List of data structures
5157:Binary decision diagram
4684:, ACM, pp. 290–304
4650:10.1145/2935764.2935768
4424:10.1145/1314690.1314692
4325:10.1145/2213977.2214082
4296:; Lagogiannis, George;
4093:10.1007/3-540-44985-X_5
3868:10.1137/1.9781611970265
3795:Sleator, Daniel Dominic
2711:Parallel priority queue
2665:min heap priority queue
119:get_front(most)_element
109:This is also known as "
5162:Directed acyclic graph
4303:Strict Fibonacci heaps
4294:Brodal, Gerth Stølting
3803:"Self-Adjusting Heaps"
3673:Third edition, p. 518.
3595:
3575:
3544:
3524:
3471:
3416:
3396:
3376:
3356:
3336:
3316:
3296:
3276:
3256:
3227:
3194:
3098:
3029:
3009:
3008:{\textstyle O(\log n)}
2951:
2927:
2889:mark is not set. This
2841:
2818:
2804:will remove the first
2794:
2773:
2772:{\textstyle O(\log n)}
2738:
2564:Scheduling (computing)
2415:'s library contains a
2405:'s library contains a
2395:'s library contains a
2383:'s library contains a
2277:) time per key, where
2267:
2209:
2173:
2137:
2089:
2061:
2033:
1999:
1971:
1943:
1902:
1866:
1830:
1799:
1763:
1727:
1611:
1553:
1458:heaps (not supporting
573:
403:'th list, and updates
306:Alternatively, when a
4748:Leiserson, Charles E.
4495:Leiserson, Charles E.
4154:Pettie, Seth (2005).
4141:10.1145/320211.320214
3756:Leiserson, Charles E.
3734:, 48(3):533-551, 1994
3645:Leiserson, Charles E.
3596:
3576:
3545:
3525:
3472:
3417:
3397:
3377:
3357:
3337:
3317:
3297:
3277:
3257:
3222:
3195:
3099:
3030:
3010:
2962:shared-memory setting
2952:
2928:
2839:
2819:
2795:
2774:
2739:
2673:minimum spanning tree
2615:algorithms, like the
2437:framework contains a
2227:
2210:
2174:
2138:
2090:
2088:{\displaystyle n^{2}}
2062:
2060:{\displaystyle n^{2}}
2034:
2000:
1998:{\displaystyle n^{2}}
1972:
1970:{\displaystyle n^{2}}
1944:
1942:{\displaystyle n^{2}}
1903:
1867:
1831:
1800:
1764:
1728:
1612:
1554:
574:
205:Naive implementations
31:similar to a regular
5028:Unrolled linked list
4374:Goodrich, Michael T.
4208:"Rank-pairing heaps"
4179:10.1109/SFCS.2005.75
3799:Tarjan, Robert Endre
3585:
3565:
3534:
3481:
3430:
3406:
3386:
3366:
3346:
3326:
3306:
3286:
3266:
3246:
3108:
3051:
3039:can be applied by a
3035:smallest elements.
3019:
2984:
2941:
2917:
2808:
2784:
2748:
2719:
2583:Dijkstra's algorithm
2573:Dijkstra's algorithm
2488:media access control
2450:Bandwidth management
2424:Standard PHP Library
2281:is some function of
2184:
2148:
2112:
2072:
2044:
2023:
1982:
1954:
1926:
1877:
1841:
1820:
1774:
1738:
1702:
1662:, once the layer of
1563:
1519:
528:
263:Usual implementation
132:" in the literature.
86:insert_with_priority
5206:Abstract data types
5076:Self-balancing tree
4788:std::priority_queue
4280:10.1145/28869.28874
4038:Theory of 2–3 Heaps
2966:binary search trees
2909:-element operations
2617:A* search algorithm
2502:. Examples include
2500:best-effort service
2484:local area networks
2350:std::priority_queue
1440:) for binary heaps.
126:get_minimum_element
115:get_maximum_element
5056:Binary search tree
4921:Double-ended queue
4786:C++ reference for
4534:"Prim's Algorithm"
4411:Journal of the ACM
3862:. pp. 38–42.
3728:Michael L. Fredman
3591:
3571:
3540:
3520:
3467:
3412:
3392:
3372:
3352:
3332:
3312:
3292:
3272:
3252:
3228:
3190:
3094:
3025:
3005:
2972:. In particular,
2947:
2923:
2842:
2814:
2790:
2769:
2734:
2529:, phone lines and
2523:local area network
2512:quality of service
2352:as one of the STL
2265:in constant time.
2205:
2169:
2133:
2085:
2057:
2029:
1995:
1967:
1939:
1898:
1862:
1826:
1795:
1759:
1723:
1660:sorting algorithms
1607:
1549:
569:
439:van Emde Boas tree
419:, then increments
29:abstract data type
5188:
5187:
4990:Hashed array tree
4889:Associative array
4752:Rivest, Ronald L.
4744:Cormen, Thomas H.
4717:978-3-030-25208-3
4659:978-1-4503-4210-0
4499:Rivest, Ronald L.
4491:Cormen, Thomas H.
4378:Tamassia, Roberto
4334:978-1-4503-1245-5
4298:Tarjan, Robert E.
4245:Tarjan, Robert E.
4227:10.1137/100785351
4215:SIAM J. Computing
4206:(November 2011).
4204:Tarjan, Robert E.
3877:978-0-89871-187-5
3801:(February 1986).
3760:Rivest, Ronald L.
3752:Cormen, Thomas H.
3701:978-1-849-96720-4
3649:Rivest, Ronald L.
3641:Cormen, Thomas H.
3447:
3143:
3086:
2976:corresponds to a
2737:{\textstyle O(1)}
2613:Best-first search
2506:(an amendment to
2218:
2217:
2032:{\displaystyle n}
1829:{\displaystyle n}
1636:is not supported.
1597:
1482:. Here, it makes
1395:
1394:
608:time complexities
349:Specialized heaps
106:, and return it.
5213:
5013:Association list
4845:
4838:
4831:
4822:
4821:
4789:
4775:
4730:
4729:
4695:
4686:
4685:
4677:
4671:
4670:
4643:
4627:
4621:
4620:
4608:
4602:
4601:
4583:
4559:
4550:
4549:
4547:
4545:
4530:
4524:
4522:
4487:
4481:
4480:
4474:
4466:
4464:
4463:
4457:
4450:
4442:
4436:
4435:
4402:
4396:
4395:
4370:
4364:
4363:
4362:, pp. 52–58
4357:
4349:Brodal, Gerth S.
4345:
4339:
4338:
4318:
4308:
4290:
4284:
4283:
4273:
4253:
4237:
4231:
4230:
4221:(6): 1463–1485.
4212:
4199:
4193:
4192:
4172:
4162:
4151:
4145:
4144:
4124:
4112:
4106:
4105:
4086:
4076:
4066:
4052:
4046:
4045:
4043:
4029:
4023:
4022:
4001:
3995:
3994:
3993:
3973:
3964:
3963:
3961:
3960:
3946:
3940:
3939:
3937:
3936:
3930:
3924:. Archived from
3915:
3897:
3888:
3882:
3881:
3852:
3843:
3842:
3824:
3791:
3780:
3779:
3748:
3735:
3725:
3719:
3712:
3706:
3705:
3690:(2nd ed.).
3680:
3674:
3672:
3637:
3600:
3598:
3597:
3592:
3580:
3578:
3577:
3572:
3549:
3547:
3546:
3541:
3529:
3527:
3526:
3521:
3476:
3474:
3473:
3468:
3448:
3440:
3421:
3419:
3418:
3413:
3401:
3399:
3398:
3393:
3381:
3379:
3378:
3373:
3361:
3359:
3358:
3353:
3341:
3339:
3338:
3333:
3321:
3319:
3318:
3313:
3301:
3299:
3298:
3293:
3281:
3279:
3278:
3273:
3261:
3259:
3258:
3253:
3199:
3197:
3196:
3191:
3144:
3136:
3103:
3101:
3100:
3095:
3087:
3079:
3034:
3032:
3031:
3026:
3014:
3012:
3011:
3006:
2956:
2954:
2953:
2948:
2932:
2930:
2929:
2924:
2823:
2821:
2820:
2815:
2799:
2797:
2796:
2791:
2778:
2776:
2775:
2770:
2743:
2741:
2740:
2735:
2681:undirected graph
2669:Prim's algorithm
2428:SplPriorityQueue
2388:
2321:( log
2317:(1) pulling and
2214:
2212:
2211:
2206:
2178:
2176:
2175:
2170:
2142:
2140:
2139:
2134:
2094:
2092:
2091:
2086:
2084:
2083:
2066:
2064:
2063:
2058:
2056:
2055:
2038:
2036:
2035:
2030:
2004:
2002:
2001:
1996:
1994:
1993:
1976:
1974:
1973:
1968:
1966:
1965:
1948:
1946:
1945:
1940:
1938:
1937:
1907:
1905:
1904:
1899:
1871:
1869:
1868:
1863:
1835:
1833:
1832:
1827:
1804:
1802:
1801:
1796:
1768:
1766:
1765:
1760:
1732:
1730:
1729:
1724:
1669:
1668:
1637:
1626:
1617:
1616:
1614:
1613:
1608:
1600:
1599:
1598:
1581:
1558:
1556:
1555:
1550:
1513:
1507:
1452:
1441:
1420:) time whenever
1403:
1295:Strict Fibonacci
1267:
1258:
1210:
1201:
1153:
1140:
1114:
1101:
1092:
1083:
1070:
1024:
1009:
904:
799:
786:
773:
760:
747:
637:
636:
613:
578:
576:
575:
570:
550:
433:
422:
418:
410:
402:
398:
394:
390:
383:
111:pop_element(Off)
104:highest priority
21:computer science
5221:
5220:
5216:
5215:
5214:
5212:
5211:
5210:
5201:Priority queues
5191:
5190:
5189:
5184:
5171:
5143:
5037:
5033:XOR linked list
4999:
4975:Circular buffer
4956:
4875:
4854:
4852:Data structures
4849:
4811:by Stefan Xenos
4787:
4782:
4772:
4756:Stein, Clifford
4739:
4737:Further reading
4734:
4733:
4718:
4696:
4689:
4678:
4674:
4660:
4628:
4624:
4609:
4605:
4560:
4553:
4543:
4541:
4532:
4531:
4527:
4519:
4503:Stein, Clifford
4488:
4484:
4468:
4467:
4461:
4459:
4455:
4448:
4446:"Archived copy"
4444:
4443:
4439:
4403:
4399:
4392:
4371:
4367:
4355:
4346:
4342:
4335:
4316:10.1.1.233.1740
4306:
4291:
4287:
4271:10.1.1.309.8927
4251:
4238:
4234:
4210:
4200:
4196:
4189:
4160:
4152:
4148:
4122:
4113:
4109:
4103:
4084:10.1.1.748.7812
4064:
4053:
4049:
4041:
4030:
4026:
4019:
4002:
3998:
3974:
3967:
3958:
3956:
3948:
3947:
3943:
3934:
3932:
3928:
3913:10.1.1.353.7888
3895:
3889:
3885:
3878:
3853:
3846:
3831:10.1137/0215004
3792:
3783:
3776:
3749:
3738:
3726:
3722:
3713:
3709:
3702:
3681:
3677:
3669:
3653:Stein, Clifford
3638:
3634:
3629:
3607:
3586:
3583:
3582:
3566:
3563:
3562:
3535:
3532:
3531:
3482:
3479:
3478:
3439:
3431:
3428:
3427:
3407:
3404:
3403:
3387:
3384:
3383:
3367:
3364:
3363:
3347:
3344:
3343:
3327:
3324:
3323:
3307:
3304:
3303:
3287:
3284:
3283:
3267:
3264:
3263:
3247:
3244:
3243:
3135:
3109:
3106:
3105:
3078:
3052:
3049:
3048:
3020:
3017:
3016:
2985:
2982:
2981:
2942:
2939:
2938:
2918:
2915:
2914:
2911:
2830:
2809:
2806:
2805:
2785:
2782:
2781:
2749:
2746:
2745:
2720:
2717:
2716:
2713:
2661:
2649:
2610:
2595:
2575:
2568:queueing theory
2550:
2510:which provides
2452:
2447:
2435:Core Foundation
2384:
2368:Boost libraries
2360:class templates
2344:(STL), and the
2331:
2309: log
2223:
2185:
2182:
2181:
2149:
2146:
2145:
2113:
2110:
2109:
2079:
2075:
2073:
2070:
2069:
2051:
2047:
2045:
2042:
2041:
2024:
2021:
2020:
1989:
1985:
1983:
1980:
1979:
1961:
1957:
1955:
1952:
1951:
1933:
1929:
1927:
1924:
1923:
1878:
1875:
1874:
1842:
1839:
1838:
1821:
1818:
1817:
1775:
1772:
1771:
1739:
1736:
1735:
1703:
1700:
1699:
1651:
1646:
1641:
1640:
1627:
1620:
1580:
1576:
1572:
1564:
1561:
1560:
1559:upper bound of
1520:
1517:
1516:
1515:Lower bound of
1514:
1510:
1453:
1444:
1404:
1400:
604:
546:
529:
526:
525:
508:implements the
424:
420:
416:
405:top ← min(top,
404:
400:
396:
392:
388:
387:plus a pointer
381:
358:data structures
351:
301:Fibonacci heaps
287:) to build the
265:
260:
254:
247:(1) pull time)
237:
231:
207:
202:
73:
17:
12:
11:
5:
5219:
5209:
5208:
5203:
5186:
5185:
5183:
5182:
5176:
5173:
5172:
5170:
5169:
5164:
5159:
5153:
5151:
5145:
5144:
5142:
5141:
5140:
5139:
5129:
5128:
5127:
5125:Hilbert R-tree
5122:
5117:
5107:
5106:
5105:
5103:Fibonacci heap
5100:
5095:
5085:
5084:
5083:
5078:
5073:
5071:Red–black tree
5068:
5063:
5053:
5047:
5045:
5039:
5038:
5036:
5035:
5030:
5025:
5020:
5015:
5009:
5007:
5001:
5000:
4998:
4997:
4992:
4987:
4982:
4977:
4972:
4966:
4964:
4958:
4957:
4955:
4954:
4953:
4952:
4947:
4937:
4936:
4935:
4928:Priority queue
4925:
4924:
4923:
4913:
4908:
4903:
4902:
4901:
4896:
4885:
4883:
4877:
4876:
4874:
4873:
4868:
4862:
4860:
4856:
4855:
4848:
4847:
4840:
4833:
4825:
4819:
4818:
4812:
4806:
4800:
4791:
4781:
4780:External links
4778:
4777:
4776:
4770:
4738:
4735:
4732:
4731:
4716:
4687:
4672:
4658:
4622:
4603:
4581:10.1.1.67.1310
4574:(5): 609–627.
4551:
4525:
4517:
4482:
4437:
4406:Thorup, Mikkel
4397:
4390:
4365:
4340:
4333:
4285:
4264:(3): 596–615.
4232:
4194:
4187:
4170:10.1.1.549.471
4146:
4135:(4): 473–501.
4107:
4101:
4047:
4033:Takaoka, Tadao
4024:
4017:
4005:Okasaki, Chris
3996:
3984:(6): 839–857,
3965:
3941:
3883:
3876:
3856:Tarjan, Robert
3844:
3822:10.1.1.93.6678
3781:
3774:
3736:
3720:
3707:
3700:
3684:Skiena, Steven
3675:
3667:
3631:
3630:
3628:
3625:
3624:
3623:
3618:
3613:
3606:
3603:
3594:{\textstyle k}
3590:
3574:{\textstyle k}
3570:
3543:{\textstyle n}
3539:
3519:
3516:
3513:
3510:
3507:
3504:
3501:
3498:
3495:
3492:
3489:
3486:
3466:
3463:
3460:
3457:
3454:
3451:
3446:
3443:
3438:
3435:
3415:{\textstyle k}
3411:
3395:{\textstyle k}
3391:
3375:{\textstyle m}
3371:
3355:{\textstyle k}
3351:
3335:{\textstyle k}
3331:
3315:{\textstyle p}
3311:
3295:{\textstyle k}
3291:
3275:{\textstyle m}
3271:
3255:{\textstyle m}
3251:
3202:k_decrease-key
3189:
3186:
3183:
3180:
3177:
3174:
3171:
3168:
3165:
3162:
3159:
3156:
3153:
3150:
3147:
3142:
3139:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3093:
3090:
3085:
3082:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3056:
3028:{\textstyle k}
3024:
3004:
3001:
2998:
2995:
2992:
2989:
2950:{\textstyle k}
2946:
2926:{\textstyle k}
2922:
2910:
2904:
2895:
2894:
2880:
2829:
2826:
2817:{\textstyle k}
2813:
2793:{\textstyle k}
2789:
2768:
2765:
2762:
2759:
2756:
2753:
2733:
2730:
2727:
2724:
2712:
2709:
2660:
2657:
2648:
2645:
2629:weighted graph
2609:
2606:
2598:Huffman coding
2594:
2593:Huffman coding
2591:
2579:adjacency list
2574:
2571:
2549:
2546:
2531:coaxial cables
2451:
2448:
2446:
2443:
2417:container/heap
2330:
2327:
2222:
2219:
2216:
2215:
2204:
2201:
2198:
2195:
2192:
2189:
2179:
2168:
2165:
2162:
2159:
2156:
2153:
2143:
2132:
2129:
2126:
2123:
2120:
2117:
2107:
2102:
2096:
2095:
2082:
2078:
2067:
2054:
2050:
2039:
2028:
2018:
2012:
2010:Insertion sort
2006:
2005:
1992:
1988:
1977:
1964:
1960:
1949:
1936:
1932:
1921:
1915:
1913:Selection sort
1909:
1908:
1897:
1894:
1891:
1888:
1885:
1882:
1872:
1861:
1858:
1855:
1852:
1849:
1846:
1836:
1825:
1815:
1814:Leonardo Heap
1812:
1806:
1805:
1794:
1791:
1788:
1785:
1782:
1779:
1769:
1758:
1755:
1752:
1749:
1746:
1743:
1733:
1722:
1719:
1716:
1713:
1710:
1707:
1697:
1692:
1686:
1685:
1682:
1679:
1676:
1673:
1650:
1647:
1645:
1642:
1639:
1638:
1618:
1606:
1603:
1596:
1593:
1590:
1587:
1584:
1579:
1575:
1571:
1568:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1508:
1498:still runs in
1442:
1397:
1396:
1393:
1392:
1382:
1376:
1370:
1364:
1354:
1348:
1342:
1341:
1331:
1325:
1319:
1313:
1303:
1297:
1291:
1290:
1280:
1274:
1268:
1259:
1246:
1240:
1234:
1233:
1223:
1217:
1211:
1202:
1189:
1183:
1177:
1176:
1166:
1160:
1154:
1141:
1128:
1122:
1116:
1115:
1102:
1093:
1084:
1071:
1058:
1052:
1050:Bottom-up skew
1046:
1045:
1035:
1025:
1016:
1010:
997:
991:
985:
984:
974:
964:
958:
948:
938:
932:
926:
925:
915:
905:
896:
886:
876:
870:
864:
863:
853:
843:
833:
823:
813:
807:
801:
800:
787:
774:
761:
748:
735:
729:
723:
722:
712:
702:
692:
682:
672:
666:
660:
659:
656:
653:
650:
647:
644:
641:
632:Big O notation
603:
600:
581:
580:
568:
565:
562:
559:
556:
553:
549:
545:
542:
539:
536:
533:
524:operations in
494:
477:operations in
435:
350:
347:
264:
261:
255:
249:
232:
226:
224:) pull time),
206:
203:
201:
200:Implementation
198:
151:
150:
149:
148:
141:delete_element
133:
122:
97:
83:
72:
69:
25:priority queue
15:
9:
6:
4:
3:
2:
5218:
5207:
5204:
5202:
5199:
5198:
5196:
5181:
5178:
5177:
5174:
5168:
5165:
5163:
5160:
5158:
5155:
5154:
5152:
5150:
5146:
5138:
5135:
5134:
5133:
5130:
5126:
5123:
5121:
5118:
5116:
5113:
5112:
5111:
5108:
5104:
5101:
5099:
5098:Binomial heap
5096:
5094:
5091:
5090:
5089:
5086:
5082:
5079:
5077:
5074:
5072:
5069:
5067:
5064:
5062:
5059:
5058:
5057:
5054:
5052:
5049:
5048:
5046:
5044:
5040:
5034:
5031:
5029:
5026:
5024:
5021:
5019:
5016:
5014:
5011:
5010:
5008:
5006:
5002:
4996:
4995:Sparse matrix
4993:
4991:
4988:
4986:
4983:
4981:
4980:Dynamic array
4978:
4976:
4973:
4971:
4968:
4967:
4965:
4963:
4959:
4951:
4948:
4946:
4943:
4942:
4941:
4938:
4934:
4931:
4930:
4929:
4926:
4922:
4919:
4918:
4917:
4914:
4912:
4909:
4907:
4904:
4900:
4897:
4895:
4892:
4891:
4890:
4887:
4886:
4884:
4882:
4878:
4872:
4869:
4867:
4864:
4863:
4861:
4857:
4853:
4846:
4841:
4839:
4834:
4832:
4827:
4826:
4823:
4816:
4813:
4810:
4807:
4804:
4801:
4799:
4795:
4792:
4790:
4784:
4783:
4773:
4771:0-262-03293-7
4767:
4763:
4762:
4757:
4753:
4749:
4745:
4741:
4740:
4727:
4723:
4719:
4713:
4709:
4705:
4701:
4694:
4692:
4683:
4676:
4669:
4665:
4661:
4655:
4651:
4647:
4642:
4637:
4633:
4626:
4618:
4614:
4607:
4599:
4595:
4591:
4587:
4582:
4577:
4573:
4569:
4565:
4558:
4556:
4539:
4535:
4529:
4520:
4518:0-262-03384-4
4514:
4510:
4509:
4504:
4500:
4496:
4492:
4486:
4478:
4472:
4454:
4447:
4441:
4433:
4429:
4425:
4421:
4417:
4413:
4412:
4407:
4401:
4393:
4391:0-471-46983-1
4387:
4383:
4379:
4375:
4369:
4361:
4354:
4350:
4344:
4336:
4330:
4326:
4322:
4317:
4312:
4305:
4304:
4299:
4295:
4289:
4281:
4277:
4272:
4267:
4263:
4259:
4258:
4250:
4247:(July 1987).
4246:
4242:
4236:
4228:
4224:
4220:
4216:
4209:
4205:
4198:
4190:
4188:0-7695-2468-0
4184:
4180:
4176:
4171:
4166:
4159:
4158:
4150:
4142:
4138:
4134:
4130:
4129:
4121:
4118:(July 1999).
4117:
4111:
4104:
4102:3-540-67690-2
4098:
4094:
4090:
4085:
4080:
4075:
4070:
4063:
4062:
4057:
4051:
4040:
4039:
4034:
4028:
4020:
4018:9780521631242
4014:
4010:
4006:
4000:
3992:
3987:
3983:
3979:
3972:
3970:
3955:
3954:brilliant.org
3951:
3945:
3931:on 2016-02-05
3927:
3923:
3919:
3914:
3909:
3905:
3901:
3900:J. Algorithms
3894:
3887:
3879:
3873:
3869:
3865:
3861:
3857:
3851:
3849:
3840:
3836:
3832:
3828:
3823:
3818:
3814:
3810:
3809:
3804:
3800:
3796:
3790:
3788:
3786:
3777:
3775:0-262-03141-8
3771:
3767:
3766:
3761:
3757:
3753:
3747:
3745:
3743:
3741:
3733:
3729:
3724:
3717:
3711:
3703:
3697:
3693:
3689:
3685:
3679:
3670:
3668:0-262-03293-7
3664:
3660:
3659:
3654:
3650:
3646:
3642:
3636:
3632:
3622:
3621:Job scheduler
3619:
3617:
3616:Command queue
3614:
3612:
3609:
3608:
3602:
3588:
3568:
3558:
3556:
3555:k_extract-min
3551:
3537:
3511:
3505:
3502:
3499:
3496:
3487:
3484:
3458:
3452:
3449:
3444:
3441:
3433:
3425:
3424:k_extract-min
3409:
3389:
3369:
3349:
3329:
3309:
3289:
3269:
3249:
3241:
3240:k_extract-min
3236:
3233:
3225:
3224:k_extract-min
3221:
3217:
3213:
3211:
3207:
3203:
3184:
3181:
3178:
3175:
3169:
3166:
3160:
3157:
3154:
3151:
3148:
3140:
3137:
3132:
3129:
3123:
3120:
3117:
3111:
3083:
3080:
3075:
3072:
3066:
3063:
3060:
3054:
3046:
3042:
3038:
3022:
2999:
2996:
2993:
2987:
2979:
2975:
2974:k_extract-min
2971:
2967:
2963:
2958:
2944:
2936:
2935:k_extract-min
2920:
2908:
2903:
2901:
2892:
2888:
2884:
2881:
2878:
2875:
2874:
2873:
2871:
2867:
2863:
2859:
2855:
2851:
2847:
2838:
2834:
2825:
2811:
2803:
2787:
2763:
2760:
2757:
2751:
2728:
2722:
2708:
2706:
2702:
2698:
2694:
2690:
2686:
2682:
2678:
2674:
2670:
2666:
2656:
2654:
2644:
2642:
2638:
2634:
2630:
2626:
2622:
2618:
2614:
2605:
2603:
2599:
2590:
2586:
2584:
2580:
2570:
2569:
2565:
2561:
2557:
2555:
2545:
2543:
2540:
2534:
2532:
2528:
2524:
2520:
2517:
2513:
2509:
2505:
2501:
2497:
2493:
2489:
2485:
2480:
2477:
2473:
2468:
2464:
2461:
2457:
2442:
2440:
2436:
2431:
2429:
2425:
2420:
2418:
2414:
2410:
2408:
2407:PriorityQueue
2404:
2400:
2398:
2397:PriorityQueue
2394:
2390:
2387:
2386:PriorityQueue
2382:
2378:
2376:
2371:
2369:
2365:
2361:
2358:
2355:
2351:
2347:
2343:
2338:
2336:
2326:
2325:) insertion.
2324:
2320:
2316:
2312:
2308:
2304:
2300:
2296:
2292:
2288:
2284:
2280:
2276:
2272:
2266:
2264:
2260:
2256:
2252:
2248:
2244:
2240:
2236:
2232:
2226:
2199:
2193:
2190:
2187:
2180:
2163:
2157:
2154:
2151:
2144:
2127:
2121:
2118:
2115:
2108:
2106:
2103:
2101:
2098:
2080:
2076:
2068:
2052:
2048:
2040:
2026:
2019:
2017:
2013:
2011:
2008:
1990:
1986:
1978:
1962:
1958:
1950:
1934:
1930:
1922:
1920:
1916:
1914:
1911:
1892:
1886:
1883:
1880:
1873:
1856:
1850:
1847:
1844:
1837:
1823:
1816:
1813:
1811:
1808:
1789:
1783:
1780:
1777:
1770:
1753:
1747:
1744:
1741:
1734:
1717:
1711:
1708:
1705:
1698:
1696:
1693:
1691:
1688:
1683:
1680:
1677:
1674:
1671:
1670:
1667:
1665:
1661:
1656:
1635:
1631:
1625:
1623:
1604:
1594:
1591:
1588:
1585:
1582:
1577:
1573:
1566:
1546:
1540:
1537:
1534:
1531:
1528:
1512:
1505:
1501:
1497:
1493:
1489:
1485:
1481:
1477:
1473:
1469:
1465:
1461:
1457:
1451:
1449:
1447:
1439:
1435:
1431:
1427:
1423:
1419:
1415:
1411:
1407:
1402:
1398:
1390:
1386:
1383:
1380:
1377:
1374:
1371:
1368:
1365:
1362:
1358:
1355:
1352:
1349:
1347:
1344:
1343:
1339:
1335:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1307:
1304:
1301:
1298:
1296:
1293:
1292:
1288:
1284:
1281:
1278:
1275:
1272:
1269:
1263:
1260:
1254:
1250:
1247:
1244:
1241:
1239:
1236:
1235:
1231:
1227:
1224:
1221:
1218:
1215:
1212:
1206:
1203:
1197:
1193:
1190:
1187:
1184:
1182:
1179:
1178:
1174:
1170:
1167:
1164:
1161:
1158:
1155:
1149:
1145:
1142:
1136:
1132:
1129:
1126:
1123:
1121:
1118:
1117:
1110:
1106:
1103:
1097:
1094:
1088:
1085:
1079:
1075:
1072:
1066:
1062:
1059:
1056:
1053:
1051:
1048:
1047:
1043:
1039:
1036:
1033:
1029:
1026:
1020:
1017:
1014:
1011:
1005:
1001:
998:
995:
992:
990:
987:
986:
982:
978:
975:
972:
968:
965:
962:
959:
956:
952:
949:
946:
942:
939:
936:
933:
931:
930:Skew binomial
928:
927:
923:
919:
916:
913:
909:
906:
900:
897:
894:
890:
887:
884:
880:
877:
874:
871:
869:
866:
865:
861:
857:
854:
851:
847:
844:
841:
837:
834:
831:
827:
824:
821:
817:
814:
811:
808:
806:
803:
802:
795:
791:
788:
782:
778:
775:
769:
765:
762:
756:
752:
749:
743:
739:
736:
733:
730:
728:
725:
724:
720:
716:
713:
710:
706:
703:
700:
696:
693:
690:
686:
683:
680:
676:
673:
670:
667:
665:
662:
661:
657:
654:
651:
649:decrease-key
648:
645:
642:
639:
638:
635:
633:
629:
625:
621:
617:
609:
599:
596:
592:
590:
586:
563:
560:
557:
554:
551:
547:
543:
540:
537:
531:
523:
519:
516:(1) time and
515:
512:operation in
511:
507:
503:
499:
495:
492:
488:
484:
480:
476:
472:
468:
464:
460:
456:
452:
448:
444:
441:supports the
440:
436:
431:
427:
414:
408:
386:
379:
375:
371:
367:
363:
362:
361:
359:
356:
346:
344:
339:
337:
333:
329:
325:
321:
317:
313:
309:
304:
302:
298:
297:pairing heaps
294:
290:
286:
282:
278:
274:
270:
258:
252:
248:
246:
242:
235:
229:
225:
223:
219:
215:
210:
197:
194:
190:
186:
184:
179:
177:
173:
171:
166:
162:
158:
157:
153:In addition,
146:
142:
138:
134:
131:
127:
123:
120:
116:
112:
108:
107:
105:
101:
98:
95:
91:
87:
84:
81:
78:
77:
76:
68:
66:
62:
58:
54:
50:
45:
42:
38:
34:
30:
26:
22:
4950:Disjoint-set
4927:
4798:Lee Killough
4794:Descriptions
4760:
4699:
4681:
4675:
4631:
4625:
4616:
4606:
4571:
4567:
4544:12 September
4542:. Retrieved
4528:
4507:
4485:
4460:. Retrieved
4440:
4415:
4409:
4400:
4381:
4368:
4359:
4343:
4302:
4288:
4261:
4255:
4235:
4218:
4214:
4197:
4156:
4149:
4132:
4126:
4110:
4060:
4056:Iacono, John
4050:
4044:, p. 12
4037:
4027:
4008:
3999:
3981:
3977:
3957:. Retrieved
3953:
3944:
3933:. Retrieved
3926:the original
3903:
3899:
3886:
3859:
3815:(1): 52–69.
3812:
3806:
3764:
3731:
3723:
3715:
3710:
3687:
3678:
3657:
3635:
3559:
3554:
3552:
3426:is expected
3423:
3239:
3237:
3231:
3229:
3223:
3214:
3209:
3205:
3201:
3044:
3040:
3036:
2977:
2973:
2959:
2937:deletes the
2934:
2912:
2906:
2896:
2890:
2886:
2882:
2876:
2869:
2865:
2843:
2831:
2801:
2714:
2697:decrease-key
2696:
2692:
2688:
2684:
2671:to find the
2662:
2650:
2632:
2611:
2596:
2587:
2576:
2559:
2558:
2551:
2535:
2504:IEEE 802.11e
2481:
2474:stream of a
2453:
2445:Applications
2439:CFBinaryHeap
2432:
2421:
2411:
2401:
2391:
2379:
2372:
2339:
2332:
2322:
2318:
2314:
2310:
2306:
2302:
2298:
2294:
2290:
2282:
2278:
2274:
2270:
2268:
2262:
2261:)) time and
2258:
2254:
2250:
2246:
2242:
2238:
2234:
2230:
2228:
2224:
1652:
1634:decrease-key
1633:
1511:
1503:
1499:
1495:
1491:
1487:
1483:
1479:
1475:
1471:
1467:
1463:
1460:decrease-key
1459:
1437:
1433:
1429:
1425:
1421:
1417:
1413:
1409:
1405:
1401:
1388:
1384:
1378:
1372:
1366:
1360:
1356:
1350:
1337:
1333:
1327:
1321:
1315:
1309:
1305:
1299:
1286:
1282:
1276:
1270:
1261:
1252:
1248:
1242:
1229:
1225:
1219:
1213:
1204:
1195:
1191:
1185:
1181:Rank-pairing
1172:
1168:
1162:
1156:
1147:
1143:
1134:
1130:
1124:
1108:
1104:
1095:
1086:
1077:
1073:
1064:
1060:
1054:
1041:
1037:
1031:
1027:
1018:
1012:
1003:
999:
993:
980:
976:
970:
966:
960:
954:
950:
944:
940:
934:
921:
917:
911:
907:
898:
892:
888:
882:
878:
872:
859:
855:
849:
845:
839:
835:
829:
825:
819:
815:
809:
793:
789:
780:
776:
767:
763:
754:
750:
741:
737:
731:
718:
714:
708:
704:
698:
694:
688:
684:
678:
674:
668:
627:
623:
619:
615:
605:
593:
588:
582:
521:
517:
513:
509:
490:
486:
482:
478:
474:
470:
466:
462:
458:
454:
450:
446:
442:
429:
425:
412:
406:
391:, initially
385:linked lists
378:bucket queue
373:
369:
365:
352:
340:
327:
323:
319:
315:
311:
305:
292:
284:
280:
276:
272:
266:
256:
250:
244:
240:
238:
233:
227:
221:
217:
213:
211:
208:
187:
182:
180:
175:
169:
164:
160:
154:
152:
144:
140:
136:
129:
125:
118:
114:
110:
103:
99:
85:
79:
74:
46:
40:
24:
18:
5093:Binary heap
5018:Linked list
4619:(in German)
3906:: 126–153.
3611:Batch queue
2883:extract-min
2693:extract-min
2542:Callmanager
2527:power lines
2508:IEEE 802.11
1664:abstraction
1466:to that of
646:delete-min
522:extract-min
498:Fusion tree
489:(2), where
471:predecessor
467:extract-max
463:extract-min
413:Extract-min
374:extract-min
336:linked list
63:or with an
61:linked list
44:undefined.
5195:Categories
5081:Splay tree
4985:Hash table
4866:Collection
4641:1602.02120
4462:2011-02-10
3959:2019-09-30
3935:2016-01-28
3627:References
3206:difference
2868:mark. The
2802:extractMin
1917:Unordered
1810:Smoothsort
1630:persistent
1502:(log
1496:delete-min
1494:is) while
1476:delete-min
1472:delete-min
1456:persistent
1428:(log
1359:(log
1308:(log
1251:(log
1194:(log
1146:(log
1133:(log
1076:(log
1063:(log
1030:(log
1002:(log
969:(log
953:(log
943:(log
910:(log
891:(log
881:(log
848:(log
838:(log
828:(log
818:(log
779:(log
766:(log
753:(log
740:(log
697:(log
687:(log
677:(log
658:make-heap
640:Operation
475:successor]
364:When only
71:Operations
5137:Hash tree
5023:Skip list
4970:Bit array
4871:Container
4803:libpqueue
4726:201692657
4576:CiteSeerX
4505:(2009) .
4418:(6): 28.
4311:CiteSeerX
4266:CiteSeerX
4165:CiteSeerX
4079:CiteSeerX
4074:1110.4428
3908:CiteSeerX
3839:0097-5397
3817:CiteSeerX
3506:
3500:⋅
3491:Ω
3453:
3208:and then
3182:
3158:
3124:
3067:
2997:
2900:See image
2877:insert(e)
2846:skip list
2761:
2677:connected
2456:bandwidth
2373:Python's
2364:iteration
2354:container
2329:Libraries
2287:word size
2194:
2158:
2122:
2100:Tree sort
1887:
1851:
1784:
1748:
1712:
1655:semantics
1592:
1586:
1538:
1532:
1523:Ω
1406:make-heap
1238:Fibonacci
643:find-min
606:Here are
561:
555:
541:
481:(log log
271:, giving
88:: add an
41:priority.
5066:AVL tree
4945:Multiset
4894:Multimap
4881:Abstract
4598:20995116
4538:Archived
4471:cite web
4453:Archived
4432:11494634
4351:(1996),
4300:(2012).
4035:(1999),
3762:(1990).
3686:(2010).
3605:See also
3477:, where
3232:k_insert
3045:k_insert
3037:k_insert
2862:pointers
2705:vertices
2621:vertices
2560:See also
2479:queues.
2433:Apple's
2263:find-min
2233:keys in
2014:Ordered
1690:Heapsort
1424:runs in
989:2–3 heap
868:Binomial
622:)" and "
370:find-min
165:find-min
161:find-max
80:is_empty
5120:R+ tree
5115:R* tree
5061:AA tree
4668:2897793
2689:minimum
2467:traffic
2460:network
2357:adaptor
1681:Average
1486:run in
1120:Pairing
805:Leftist
652:insert
630:)" see
510:minimum
506:Willard
502:Fredman
447:maximum
443:minimum
139:" and "
130:get-min
92:to the
90:element
5149:Graphs
5110:R-tree
5051:B-tree
5005:Linked
4962:Arrays
4768:
4724:
4714:
4666:
4656:
4596:
4578:
4515:
4430:
4388:
4331:
4313:
4268:
4185:
4167:
4099:
4081:
4015:
3910:
3874:
3837:
3819:
3772:
3698:
3665:
2891:delete
2887:delete
2870:delete
2866:delete
2701:weight
2685:insert
2663:Using
2633:fringe
2514:) and
2463:router
2247:insert
2243:delete
1684:Worst
1492:insert
1468:insert
1346:Brodal
664:Binary
518:insert
459:search
455:delete
451:insert
366:insert
251:insert
228:insert
193:queues
189:Stacks
117:" or "
27:is an
5043:Trees
4916:Queue
4911:Stack
4859:Types
4722:S2CID
4664:S2CID
4636:arXiv
4594:S2CID
4456:(PDF)
4449:(PDF)
4428:S2CID
4356:(PDF)
4307:(PDF)
4252:(PDF)
4211:(PDF)
4161:(PDF)
4123:(PDF)
4069:arXiv
4065:(PDF)
4042:(PDF)
3929:(PDF)
3896:(PDF)
3210:union
3041:union
2978:split
2960:In a
2858:array
2675:of a
2627:of a
2625:nodes
2539:Cisco
2516:ITU-T
2403:Scala
2375:heapq
2016:Array
1919:Array
655:meld
334:with
314:(log
275:(log
94:queue
65:array
55:or a
49:heaps
37:stack
33:queue
5132:Trie
5088:Heap
4906:List
4766:ISBN
4712:ISBN
4654:ISBN
4546:2014
4513:ISBN
4477:link
4386:ISBN
4329:ISBN
4183:ISBN
4097:ISBN
4013:ISBN
3872:ISBN
3835:ISSN
3770:ISBN
3696:ISBN
3663:ISBN
3530:and
3047:has
2968:and
2854:lock
2679:and
2653:ROAM
2637:SMA*
2519:G.hn
2496:IPTV
2492:VoIP
2476:VoIP
2422:The
2393:.NET
2381:Java
2340:The
2285:and
2245:and
1695:Heap
1678:Best
1672:Name
1653:The
1484:meld
1480:meld
1478:and
1464:meld
1454:For
1422:meld
1381:(1)
1375:(1)
1369:(1)
1353:(1)
1330:(1)
1324:(1)
1318:(1)
1302:(1)
1279:(1)
1273:(1)
1264:(1)
1245:(1)
1222:(1)
1216:(1)
1207:(1)
1188:(1)
1165:(1)
1159:(1)
1127:(1)
1098:(1)
1089:(1)
1057:(1)
1021:(1)
1015:(1)
996:(1)
963:(1)
937:(1)
901:(1)
875:(1)
812:(1)
734:(1)
727:Skew
671:(1)
585:peek
520:and
504:and
496:The
473:and
372:and
355:heap
326:log
289:heap
269:heap
257:pull
234:pull
191:and
156:peek
113:", "
53:list
23:, a
4940:Set
4796:by
4704:doi
4646:doi
4586:doi
4420:doi
4321:doi
4276:doi
4223:doi
4175:doi
4137:doi
4089:doi
3986:doi
3918:doi
3864:doi
3827:doi
3503:log
3450:log
3179:log
3155:log
3121:log
3064:log
2994:log
2860:of
2850:CAS
2758:log
2744:or
2667:in
2623:or
2533:).
2494:or
2472:RTP
2346:C++
2337:".
2249:in
2191:log
2155:log
2119:log
1884:log
1848:log
1781:log
1745:log
1709:log
1589:log
1583:log
1535:log
1529:log
1266:am.
1257:am.
1209:am.
1200:am.
1152:am.
1139:am.
1113:am.
1100:am.
1091:am.
1082:am.
1069:am.
1023:am.
1008:am.
903:am.
798:am.
785:am.
772:am.
759:am.
746:am.
612:am.
558:log
552:log
538:log
500:by
421:top
417:top
389:top
299:or
172:(1)
163:or
57:map
35:or
19:In
5197::
4754:;
4750:;
4746:;
4720:.
4710:.
4690:^
4662:,
4652:,
4644:,
4615:,
4592:.
4584:.
4572:65
4570:.
4566:.
4554:^
4501:;
4497:;
4493:;
4473:}}
4469:{{
4451:.
4426:.
4416:54
4414:.
4376:;
4358:,
4327:.
4319:.
4274:.
4262:34
4260:.
4254:.
4243:;
4219:40
4217:.
4213:.
4181:.
4173:.
4133:46
4131:.
4125:.
4095:,
4087:,
4077:,
3980:,
3968:^
3952:.
3916:.
3904:12
3902:.
3898:.
3870:.
3847:^
3833:.
3825:.
3813:15
3811:.
3805:.
3797:;
3784:^
3758:;
3754:;
3739:^
3694:.
3651:;
3647:;
3643:;
3230:A
2902:)
2695:,
2691:,
2687:,
2604:.
2566:,
2562::
2430:.
2413:Go
1621:^
1445:^
1391:)
1363:)
1340:)
1312:)
1289:)
1255:)
1232:)
1198:)
1175:)
1150:)
1137:)
1111:)
1080:)
1067:)
1044:)
1034:)
1006:)
983:)
973:)
957:)
947:)
924:)
914:)
895:)
885:)
862:)
852:)
842:)
832:)
822:)
796:)
783:)
770:)
757:)
744:)
721:)
711:)
701:)
691:)
681:)
469:,
465:,
461:,
457:,
453:,
449:,
445:,
437:A
368:,
147:".
121:".
4844:e
4837:t
4830:v
4774:.
4728:.
4706::
4648::
4638::
4600:.
4588::
4548:.
4521:.
4479:)
4465:.
4434:.
4422::
4394:.
4337:.
4323::
4282:.
4278::
4229:.
4225::
4191:.
4177::
4143:.
4139::
4091::
4071::
4021:.
3988::
3982:6
3962:.
3938:.
3920::
3880:.
3866::
3841:.
3829::
3778:.
3704:.
3671:.
3589:k
3569:k
3538:n
3518:)
3515:)
3512:p
3509:(
3497:p
3494:(
3488:=
3485:k
3465:)
3462:)
3459:n
3456:(
3445:p
3442:k
3437:(
3434:O
3410:k
3390:k
3370:m
3350:k
3330:k
3310:p
3290:k
3270:m
3250:m
3188:)
3185:n
3176:k
3173:(
3170:O
3167:=
3164:)
3161:k
3152:k
3149:+
3146:)
3141:k
3138:n
3133:+
3130:1
3127:(
3118:k
3115:(
3112:O
3092:)
3089:)
3084:k
3081:n
3076:+
3073:1
3070:(
3061:k
3058:(
3055:O
3023:k
3003:)
3000:n
2991:(
2988:O
2945:k
2921:k
2907:K
2812:k
2788:k
2767:)
2764:n
2755:(
2752:O
2732:)
2729:1
2726:(
2723:O
2323:n
2319:O
2315:O
2311:n
2307:n
2305:(
2303:O
2299:S
2297:(
2295:O
2291:O
2283:n
2279:S
2275:S
2273:(
2271:O
2259:n
2257:(
2255:S
2253:(
2251:O
2239:n
2237:(
2235:S
2231:n
2203:)
2200:n
2197:(
2188:n
2167:)
2164:n
2161:(
2152:n
2131:)
2128:n
2125:(
2116:n
2081:2
2077:n
2053:2
2049:n
2027:n
1991:2
1987:n
1963:2
1959:n
1935:2
1931:n
1896:)
1893:n
1890:(
1881:n
1860:)
1857:n
1854:(
1845:n
1824:n
1793:)
1790:n
1787:(
1778:n
1757:)
1754:n
1751:(
1742:n
1721:)
1718:n
1715:(
1706:n
1605:.
1602:)
1595:n
1578:2
1574:2
1570:(
1567:O
1547:,
1544:)
1541:n
1526:(
1504:n
1500:O
1488:Θ
1438:n
1436:(
1434:Θ
1430:n
1426:O
1418:n
1416:(
1414:Θ
1410:n
1389:n
1387:(
1385:Θ
1379:Θ
1373:Θ
1367:Θ
1361:n
1357:Θ
1351:Θ
1338:n
1336:(
1334:Θ
1328:Θ
1322:Θ
1316:Θ
1310:n
1306:Θ
1300:Θ
1287:n
1285:(
1283:Θ
1277:Θ
1271:Θ
1262:Θ
1253:n
1249:O
1243:Θ
1230:n
1228:(
1226:Θ
1220:Θ
1214:Θ
1205:Θ
1196:n
1192:O
1186:Θ
1173:n
1171:(
1169:Θ
1163:Θ
1157:Θ
1148:n
1144:o
1135:n
1131:O
1125:Θ
1109:n
1107:(
1105:Θ
1096:Θ
1087:Θ
1078:n
1074:O
1065:n
1061:O
1055:Θ
1042:n
1040:(
1038:Θ
1032:n
1028:O
1019:Θ
1013:Θ
1004:n
1000:O
994:Θ
981:n
979:(
977:Θ
971:n
967:Θ
961:Θ
955:n
951:Θ
945:n
941:Θ
935:Θ
922:n
920:(
918:Θ
912:n
908:Θ
899:Θ
893:n
889:Θ
883:n
879:Θ
873:Θ
860:n
858:(
856:Θ
850:n
846:Θ
840:n
836:Θ
830:n
826:Θ
820:n
816:Θ
810:Θ
794:n
792:(
790:Θ
781:n
777:O
768:n
764:O
755:n
751:O
742:n
738:O
732:Θ
719:n
717:(
715:Θ
709:n
707:(
705:Θ
699:n
695:Θ
689:n
685:Θ
679:n
675:Θ
669:Θ
628:f
626:(
624:Θ
620:f
618:(
616:O
589:O
567:)
564:C
548:/
544:n
535:(
532:O
514:O
491:m
487:O
483:C
479:O
432:)
430:C
428:(
426:O
409:)
407:k
401:k
397:k
393:C
382:C
328:n
324:n
322:(
320:O
316:n
312:O
293:n
285:n
283:(
281:O
277:n
273:O
245:O
241:O
222:n
220:(
218:O
214:O
176:O
170:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.