{"entities":{"Q1101212":{"pageid":1111964,"ns":120,"title":"Item:Q1101212","lastrevid":69642465,"modified":"2026-04-13T08:24:36Z","type":"item","id":"Q1101212","labels":{"en":{"language":"en","value":"Bounds for min-max heaps"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4047085"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$B0E20DB3-D77F-4D6B-9841-724AD2CA8B3B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"04607652804a93ff47d11f2f042ba2597ea4f4f4","datavalue":{"value":{"text":"Bounds for min-max heaps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1101212$E890C2B9-8980-482C-98E5-339D9E21BD1C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f052f5c995fc3a56f96f44e7fe272fd7083220e","datavalue":{"value":"0642.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101212$172A13CA-D539-4FAC-8282-FCB348AC3A49","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a30859568bde4592305b3d05b75b09801f74231","datavalue":{"value":"10.1007/BF01933726","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101212$F5DCEEE9-933A-4A20-A7F2-4B9AB7CC2D26","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca02099175697a4b54d6c3e10f20112dbf6ee98b","datavalue":{"value":{"entity-type":"item","numeric-id":170449,"id":"Q170449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$ACA4F79A-1B37-446D-9CF4-CAFD0BFBF28F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"70410dea5acbb75361da442d1567a2bb2352be3c","datavalue":{"value":{"entity-type":"item","numeric-id":579113,"id":"Q579113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$15639E67-06FD-402E-A6C9-60CF7015C698","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$BE2CBB0D-B753-4168-AA47-7995064303F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1101212$3D1D85A9-8047-4D65-AFBB-A32AD27DA488","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0dbd8e56594be10ef6158b38a007072813b679d3","datavalue":{"value":"Very recently a new data structure, called a min-max heap, was presented for implementing the double-ended priority queue. A min-max heap on n keys is constructed in O(n) time; the minimum and maximum keys are found in constant time, and the operations of deleting the minimum, deleting the maximum and inserting a new key into the heap are performed in O(log n) time. In addition, the data structure can be stored implicitly, i.e. in an array of n elements without using any additional pointers.    In this paper, we present lower bound results on the number of comparisons required, in the worst case, for the operations i) to construct a min-max heap on a given set of keys; ii) to convert a min-max heap into a max-min heap; and iii) to merge two min-max heaps into one min-max heap. New upper bounds for the convert and merge operations are also derived. It is found that the main difference between traditional heaps and min-max heaps lies in the time needed to perform the merge operation. While traditional heaps can be merged efficiently, it is shown that min-max heaps are not sublinearly mergeable. Even the seemingly simple task of converting a min-max heap into a max-min heap cannot be performed in less than linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101212$B66D21AB-1A04-4AFA-84FE-5AB33949E7B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101212$D7308E12-4F86-4869-A607-12B0FBA99CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101212$397A6020-C324-4E76-AB4C-CBC674D43FA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101212$0591912A-9B0B-46FE-8702-B7550AAE8D1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"14244d547cf3c84532377a481187932176c133ec","datavalue":{"value":"4047085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101212$512A5A37-811E-471C-A229-083167162CB1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0884ba29946682eb7d265f1ce4f2a584f7cfeb91","datavalue":{"value":"double-ended priority queue","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101212$20326B3E-FE42-4497-847E-990DB3579833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"383b9dc96960940a5131d2f58f57e85b159d7510","datavalue":{"value":"min-max heaps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101212$5F29168D-7E74-44AE-A241-A7255BC296FE","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7a91cff4de908de534b7666a65a44ef625a17f6f","datavalue":{"value":"Q62037532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101212$411B7485-1013-4519-8091-A9215EC03398","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"40511068b347a60aa196b665fa4c4acc6f9d4e19","datavalue":{"value":{"entity-type":"item","numeric-id":46612,"id":"Q46612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$B491064C-F5D0-4837-8FF2-2CF150D173EF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$8A3D4311-FC6C-4819-983C-8EBF03D77FD2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$19FF7189-DD58-4ECC-B6BD-DC07E5EA94EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d9659873ecde8ea9a78185357c1cd92dbd2e00e","datavalue":{"value":{"entity-type":"item","numeric-id":3783545,"id":"Q3783545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$1FF2376E-0930-4BE3-8941-44A9CD7BCF5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7cfb7bf7314db68e2fa5b66984e374763ca1181","datavalue":{"value":{"entity-type":"item","numeric-id":4181962,"id":"Q4181962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$9F1DE084-1502-40F4-B740-60E25C800776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d1383f49e451578f2ffe3f7b4a2f1430db18183","datavalue":{"value":{"entity-type":"item","numeric-id":3945583,"id":"Q3945583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$1456E31E-B4AB-45C7-85A8-64535C91659F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$659189CA-9484-4B24-B880-2DF21A6BE838","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0532fad157b7fde121fb251582ee5f711bbb431","datavalue":{"value":{"entity-type":"item","numeric-id":3026346,"id":"Q3026346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101212$118B2C5C-60D1-4334-8DA5-E776B6EA3A7F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7828d71e390034047fd428788476b120d767ac6","datavalue":{"value":{"entity-type":"item","numeric-id":3783545,"id":"Q3783545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e9d9c2f8df859ab4ba3370dc22e623c535b593a","datavalue":{"value":{"amount":"+0.8830935955047607","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101212$45FE034A-3F7B-4F35-A6A5-3DBB7F6F6CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4961f9d47462346fa047cb91d3d328827fc608d3","datavalue":{"value":{"entity-type":"item","numeric-id":1123594,"id":"Q1123594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67b7cf80216c5feef6cf5427cef08c10b32c905b","datavalue":{"value":{"amount":"+0.8765677213668823","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101212$1ABBD524-7670-4D04-AD6A-F909F17215F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d75f8c7f727a6fa35a2d622250248913106558ef","datavalue":{"value":{"entity-type":"item","numeric-id":4460605,"id":"Q4460605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75fa175dc9a5562a525be223ad8129fd3278fe9c","datavalue":{"value":{"amount":"+0.8408746719360352","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101212$3F64F8C4-EA3C-42F9-AAD8-D564F1351F37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8011936003e484abd9085d7f05a69a962f96b0f2","datavalue":{"value":{"entity-type":"item","numeric-id":1007603,"id":"Q1007603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3e043aa68ab8ecb0a66c7f940453ec9a70bcfa9","datavalue":{"value":{"amount":"+0.8309667110443115","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101212$2D091567-BD42-40E6-8EA6-130654435D31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d97ca6048a806c4fe759f41169bc70a44348179","datavalue":{"value":{"entity-type":"item","numeric-id":1323336,"id":"Q1323336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8c907a1099dbc30f18af15a343220ffd249b315","datavalue":{"value":{"amount":"+0.827383279800415","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101212$45A2A999-11B2-418C-9355-FF5384B63A04","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounds for min-max heaps","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounds_for_min-max_heaps"}}}}}