60:
202:
362:
compared successively with all the left hand elements of the descending nodes and the process stops when all the conditions for an interval heap are satisfied. In case if the left hand side element in the node becomes greater than the right side element at any stage, the two elements are swapped and then further comparisons are done. Finally, the root node will again contain the minimum element on the left hand side.
220:
241:
154:
595:
Read in the remaining elements. If the next element is ≤ the smallest element in the DEPQ, output this next element as part of the left group. If the next element is ≥ the largest element in the DEPQ, output this next element as part of the right group. Otherwise, remove either the max or min element
361:
In an interval heap, the minimum element is the element on the left hand side of the root node. This element is removed and returned. To fill in the vacancy created on the left hand side of the root node, an element from the last node is removed and reinserted into the root node. This element is then
325:
If the number of elements in the interval heap is odd, the new element is firstly inserted in the last node. Then, it is successively compared with the previous node elements and tested to satisfy the criteria essential for an interval heap as stated above. In case if the element does not satisfy any
209:
Half the elements are in the min PQ and the other half in the max PQ. Each element in the min PQ has a one-to-one correspondence with an element in max PQ. If the number of elements in the DEPQ is odd, one of the elements is retained in a buffer. Priority of every element in the min PQ will be less
337:. Further, it is compared successively and moved from the last node to the root until all the conditions for interval heap are satisfied. If the element lies within the interval of the parent node itself, the process is stopped then and there itself and moving of elements does not take place.
368:
In an interval heap, the maximum element is the element on the right hand side of the root node. This element is removed and returned. To fill in the vacancy created on the right hand side of the root node, an element from the last node is removed and reinserted into the root node. Further
332:
If the number of elements is even, then for the insertion of a new element an additional node is created. If the element falls to the left of the parent interval, it is considered to be in the min heap and if the element falls to the right of the parent interval, it is considered in the
231:, in this method only the leaf elements of the min and max PQ form corresponding one-to-one pairs. It is not necessary for non-leaf elements to be in a one-to-one correspondence pair. If the number of elements in the DEPQ is odd, one of the elements is retained in a buffer.
373:
Thus, with interval heaps, both the minimum and maximum elements can be removed efficiently traversing from root to leaf. Thus, a DEPQ can be obtained from an interval heap where the elements of the interval heap are the priorities of elements in the DEPQ.
596:
from the DEPQ (the choice may be made randomly or alternately); if the max element is removed, output it as part of the right group; otherwise, output the removed element as part of the left group; insert the newly input element into the DEPQ.
584:. In an external sort, there are more elements than can be held in the computer's memory. The elements to be sorted are initially on a disk and the sorted sequence is to be left on the disk. The external
309:
In this case, each node except the last contains two elements represented by the interval whereas the last node will contain a single element and is represented by the interval .
51:(items) stored in the structure. Every element in a DEPQ has a priority or value. In a DEPQ, it is possible to remove the elements in both ascending as well as descending order.
161:
In this method two different priority queues for min and max are maintained. The same elements in both the PQs are shown with the help of correspondence pointers.
59:
1113:
789:
248:
Apart from the above-mentioned correspondence methods, DEPQ's can be obtained efficiently using interval heaps. An interval heap is like an embedded
369:
comparisons are carried out on a similar basis as discussed above. Finally, the root node will again contain the max element on the right hand side.
1083:
592:
Read in as many elements as will fit into an internal DEPQ. The elements in the DEPQ will eventually be the middle group (pivot) of elements.
134:(where the minimum and maximum elements are the leftmost and rightmost leaves, respectively), or using specialized data structures like
1022:
679:
1152:
812:
817:
782:
491:
elements, the time complexities for the various functions are formulated in the table below. For pairing heaps, it is an
341:
The time required for inserting an element depends on the number of movements required to meet all the conditions and is
1147:
896:
131:
163:
Here, the minimum and maximum elements are values contained in the root nodes of min heap and max heap respectively.
1095:
862:
857:
612:
852:
1157:
891:
886:
845:
775:
1126:
1103:
1108:
908:
205:
A total correspondence heap for the elements 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11 with element 11 as buffer.
1034:
989:
951:
695:
318:
Depending on the number of elements already present in the interval heap, following cases are possible:
44:
47:, but allows for efficient removal of both the maximum and minimum, according to some ordering on the
974:
492:
326:
of the criteria, it is moved from the last node to the root until all the conditions are satisfied.
1017:
1002:
867:
827:
759:
617:
17:
936:
835:
675:
653:
145:
Generic methods of arriving at double-ended priority queues from normal priority queues are:
959:
581:
391:
elements, the time complexities for the various functions are formulated in the table below
24:
201:
979:
921:
122:
Also, the priority of any element can be changed once it has been inserted in the DEPQ.
1071:
1049:
874:
798:
40:
36:
262:
Interval represented by any node except the root is a sub-interval of the parent node.
1141:
1044:
941:
926:
654:
Data
Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues
734:
657:
249:
219:
139:
135:
240:
252:
in which each node contains two elements. It is a complete binary tree in which:
1039:
964:
1027:
931:
585:
342:
969:
916:
1066:
1012:
840:
334:
273:
266:
1061:
1007:
487:
When DEPQ's are implemented using heaps or pairing heaps consisting of
599:
Output the elements in the DEPQ, in sorted order, as the middle group.
153:
1056:
997:
767:
239:
218:
200:
152:
118:
Removes an element with maximum priority and returns this element.
112:
Removes an element with minimum priority and returns this element.
67:
A double-ended priority queue features the following operations:
1078:
720:
771:
387:
When DEPQ's are implemented using
Interval heaps consisting of
280:
Depending on the number of elements, two cases are possible -
760:
http://www.mhhe.com/engcs/compsci/sahni/enrich/c9/interval.pdf
580:
One example application of the double-ended priority queue is
699:
256:
The left element is less than or equal to the right element.
58:
223:
A leaf correspondence heap for the same elements as above.
157:
A dual structure with 14,12,4,10,8 as the members of DEPQ.
733:
Fundamentals of Data
Structures in C++ - Ellis Horowitz,
210:
than or equal to the corresponding element in the max PQ.
80:
Returns the total number of elements present in the DEPQ.
192:
is the value in the corresponding node in the min heap.
178:
is the value in the corresponding node in the max heap.
1094:
988:
950:
907:
826:
805:
63:
UML class diagram of a double-ended priority queue.
303:. Every node is then represented by the interval .
287:In this case, each node contains two elements say
74:Checks if DEPQ is empty and returns true if empty.
184:: Perform removemax() on the max heap and remove(
170:: Perform removemin() on the min heap and remove(
755:
753:
751:
749:
747:
745:
743:
130:Double-ended priority queues can be built from
783:
8:
92:Returns the element having highest priority.
674:. Cambridge University Press. p. 211.
602:Sort the left and right groups recursively.
259:Both the elements define a closed interval.
790:
776:
768:
588:is implemented using the DEPQ as follows:
497:
393:
86:Returns the element having least priority.
272:Elements on the right hand side define a
228:
265:Elements on the left hand side define a
244:Implementing a DEPQ using interval heap.
649:
647:
645:
643:
641:
639:
637:
635:
633:
629:
7:
696:"Depq - Double-Ended Priority Queue"
29:double-ended priority queue (DEPQ)
14:
1:
132:balanced binary search trees
1114:Directed acyclic word graph
880:Double-ended priority queue
1174:
613:Queue (abstract data type)
15:
1122:
188:) on the min heap, where
174:) on the max heap, where
846:Retrieval Data Structure
672:Advanced Data Structures
330:Even number of elements:
285:Even number of elements:
182:Removing the max element
168:Removing the min element
16:Not to be confused with
1153:Heaps (data structures)
1127:List of data structures
1104:Binary decision diagram
323:Odd number of elements:
307:Odd number of elements:
1109:Directed acyclic graph
245:
224:
206:
158:
64:
670:Brass, Peter (2008).
243:
222:
204:
156:
149:Dual structure method
62:
975:Unrolled linked list
493:amortized complexity
314:Inserting an element
229:total correspondence
197:Total correspondence
102:Inserts the element
1148:Abstract data types
1023:Self-balancing tree
353:Deleting an element
215:Leaf correspondence
1003:Binary search tree
868:Double-ended queue
618:Double-ended queue
246:
225:
207:
159:
65:
18:Double-ended queue
1135:
1134:
937:Hashed array tree
836:Associative array
568:
567:
480:
479:
227:In contrast to a
33:double-ended heap
1165:
960:Association list
792:
785:
778:
769:
762:
757:
738:
737:and Dinesh Mehta
731:
725:
724:
717:
711:
710:
708:
707:
698:. Archived from
692:
686:
685:
667:
661:
651:
582:external sorting
576:External sorting
504:Time Complexity
498:
400:Time Complexity
394:
25:computer science
1173:
1172:
1168:
1167:
1166:
1164:
1163:
1162:
1158:Priority queues
1138:
1137:
1136:
1131:
1118:
1090:
984:
980:XOR linked list
946:
922:Circular buffer
903:
822:
801:
799:Data structures
796:
766:
765:
758:
741:
732:
728:
719:
718:
714:
705:
703:
694:
693:
689:
682:
669:
668:
664:
652:
631:
626:
609:
578:
573:
485:
385:
380:
378:Time complexity
355:
316:
238:
232:
217:
211:
199:
162:
151:
128:
57:
21:
12:
11:
5:
1171:
1169:
1161:
1160:
1155:
1150:
1140:
1139:
1133:
1132:
1130:
1129:
1123:
1120:
1119:
1117:
1116:
1111:
1106:
1100:
1098:
1092:
1091:
1089:
1088:
1087:
1086:
1076:
1075:
1074:
1072:Hilbert R-tree
1069:
1064:
1054:
1053:
1052:
1050:Fibonacci heap
1047:
1042:
1032:
1031:
1030:
1025:
1020:
1018:Red–black tree
1015:
1010:
1000:
994:
992:
986:
985:
983:
982:
977:
972:
967:
962:
956:
954:
948:
947:
945:
944:
939:
934:
929:
924:
919:
913:
911:
905:
904:
902:
901:
900:
899:
894:
884:
883:
882:
875:Priority queue
872:
871:
870:
860:
855:
850:
849:
848:
843:
832:
830:
824:
823:
821:
820:
815:
809:
807:
803:
802:
797:
795:
794:
787:
780:
772:
764:
763:
739:
726:
712:
687:
680:
662:
628:
627:
625:
622:
621:
620:
615:
608:
605:
604:
603:
600:
597:
593:
577:
574:
572:
569:
566:
565:
558:
554:
553:
546:
542:
541:
534:
530:
529:
526:
522:
521:
518:
514:
513:
510:
506:
505:
502:
484:
481:
478:
477:
470:
466:
465:
458:
454:
453:
446:
442:
441:
438:
434:
433:
430:
426:
425:
422:
418:
417:
414:
410:
409:
406:
402:
401:
398:
384:
383:Interval heaps
381:
379:
376:
371:
370:
363:
354:
351:
339:
338:
327:
315:
312:
311:
310:
304:
278:
277:
270:
263:
260:
257:
237:
236:Interval heaps
234:
216:
213:
198:
195:
194:
193:
179:
150:
147:
127:
126:Implementation
124:
120:
119:
116:
113:
110:
107:
100:
93:
90:
87:
84:
81:
78:
75:
72:
56:
53:
41:priority queue
37:data structure
13:
10:
9:
6:
4:
3:
2:
1170:
1159:
1156:
1154:
1151:
1149:
1146:
1145:
1143:
1128:
1125:
1124:
1121:
1115:
1112:
1110:
1107:
1105:
1102:
1101:
1099:
1097:
1093:
1085:
1082:
1081:
1080:
1077:
1073:
1070:
1068:
1065:
1063:
1060:
1059:
1058:
1055:
1051:
1048:
1046:
1045:Binomial heap
1043:
1041:
1038:
1037:
1036:
1033:
1029:
1026:
1024:
1021:
1019:
1016:
1014:
1011:
1009:
1006:
1005:
1004:
1001:
999:
996:
995:
993:
991:
987:
981:
978:
976:
973:
971:
968:
966:
963:
961:
958:
957:
955:
953:
949:
943:
942:Sparse matrix
940:
938:
935:
933:
930:
928:
927:Dynamic array
925:
923:
920:
918:
915:
914:
912:
910:
906:
898:
895:
893:
890:
889:
888:
885:
881:
878:
877:
876:
873:
869:
866:
865:
864:
861:
859:
856:
854:
851:
847:
844:
842:
839:
838:
837:
834:
833:
831:
829:
825:
819:
816:
814:
811:
810:
808:
804:
800:
793:
788:
786:
781:
779:
774:
773:
770:
761:
756:
754:
752:
750:
748:
746:
744:
740:
736:
730:
727:
722:
716:
713:
702:on 2012-04-25
701:
697:
691:
688:
683:
681:9780521880374
677:
673:
666:
663:
659:
655:
650:
648:
646:
644:
642:
640:
638:
636:
634:
630:
623:
619:
616:
614:
611:
610:
606:
601:
598:
594:
591:
590:
589:
587:
583:
575:
570:
563:
559:
556:
555:
551:
547:
544:
543:
539:
535:
532:
531:
527:
524:
523:
519:
516:
515:
511:
508:
507:
503:
500:
499:
496:
494:
490:
483:Pairing heaps
482:
475:
471:
468:
467:
463:
459:
456:
455:
451:
447:
444:
443:
439:
436:
435:
431:
428:
427:
423:
420:
419:
415:
412:
411:
407:
404:
403:
399:
396:
395:
392:
390:
382:
377:
375:
367:
364:
360:
357:
356:
352:
350:
348:
344:
336:
331:
328:
324:
321:
320:
319:
313:
308:
305:
302:
299: ≤
298:
294:
290:
286:
283:
282:
281:
275:
271:
268:
264:
261:
258:
255:
254:
253:
251:
242:
235:
233:
230:
221:
214:
212:
203:
196:
191:
187:
183:
180:
177:
173:
169:
166:
165:
164:
155:
148:
146:
143:
141:
137:
133:
125:
123:
117:
114:
111:
108:
105:
101:
98:
94:
91:
88:
85:
82:
79:
76:
73:
70:
69:
68:
61:
54:
52:
50:
46:
42:
39:similar to a
38:
34:
30:
26:
19:
897:Disjoint-set
879:
735:Sartaj Sahni
729:
715:
704:. Retrieved
700:the original
690:
671:
665:
658:Sartaj Sahni
579:
571:Applications
561:
557:removeMin( )
549:
545:removeMax( )
537:
488:
486:
473:
469:removeMax( )
461:
457:removeMin( )
449:
388:
386:
372:
366:Max element:
365:
359:Min element:
358:
346:
340:
329:
322:
317:
306:
300:
296:
292:
288:
284:
279:
250:min-max heap
247:
226:
208:
189:
185:
181:
175:
171:
167:
160:
144:
140:pairing heap
136:min-max heap
129:
121:
106:in the DEPQ.
103:
96:
66:
48:
32:
28:
22:
1040:Binary heap
965:Linked list
115:removeMax()
109:removeMin()
1142:Categories
1028:Splay tree
932:Hash table
813:Collection
706:2011-10-04
624:References
586:quick sort
509:isEmpty( )
413:isEmpty( )
345:(log
190:node value
186:node value
176:node value
172:node value
55:Operations
1084:Hash tree
970:Skip list
917:Bit array
818:Container
533:insert(x)
525:getmax( )
517:getmin( )
501:Operation
445:insert(x)
429:getmax( )
421:getmin( )
397:Operation
71:isEmpty()
1013:AVL tree
892:Multiset
841:Multimap
828:Abstract
607:See also
335:max heap
274:max heap
267:min heap
89:getMax()
83:getMin()
1067:R+ tree
1062:R* tree
1008:AA tree
660:, 1999.
437:size( )
405:init( )
295:, with
1096:Graphs
1057:R-tree
998:B-tree
952:Linked
909:Arrays
721:"depq"
678:
560:O(log
548:O(log
536:O(log
472:O(log
460:O(log
448:O(log
77:size()
990:Trees
863:Queue
858:Stack
806:Types
528:O(1)
520:O(1)
512:O(1)
440:O(1)
432:O(1)
424:O(1)
416:O(1)
408:O(n)
35:is a
1079:Trie
1035:Heap
853:List
676:ISBN
291:and
138:and
95:put(
49:keys
45:heap
27:, a
887:Set
349:).
43:or
31:or
23:In
1144::
742:^
656:,
632:^
564:)
552:)
540:)
495:.
476:)
464:)
452:)
142:.
791:e
784:t
777:v
723:.
709:.
684:.
562:n
550:n
538:n
489:n
474:n
462:n
450:n
389:n
347:n
343:O
301:q
297:p
293:q
289:p
276:.
269:.
104:x
99:)
97:x
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
