{"entities":{"Q797280":{"pageid":799128,"ns":120,"title":"Item:Q797280","lastrevid":64448304,"modified":"2026-04-11T19:56:44Z","type":"item","id":"Q797280","labels":{"en":{"language":"en","value":"An algorithm for merging heaps"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3868604"}},"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":"Q797280$8308438F-ED48-4D38-9B0C-5E2D472B20F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6dae87729f3a2edcf82a5f567ef488b6e8683689","datavalue":{"value":{"text":"An algorithm for merging heaps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q797280$C25E587C-9654-4140-B320-F9F63467FDD5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e9260d5f6858a53f1443145a5658d03f9a1c7506","datavalue":{"value":"0545.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797280$F47697D8-F656-40CD-978C-94D0D105791C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6addd17f33c9f7e69cd02fd8c4fbb17b3716586a","datavalue":{"value":"10.1007/BF00264229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797280$BB70F357-372E-4ACC-88EA-3445344707CA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"297023bf7627ffcd062223534098929866a59f3e","datavalue":{"value":{"entity-type":"item","numeric-id":797279,"id":"Q797279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797280$D4D90E29-5EA7-4E42-B020-0E4EF1538C39","rank":"normal"},{"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":"Q797280$BBD5BAF5-A203-4B58-9577-9CCA9DD213B3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q797280$138AA73B-7CB2-41E4-989B-DD46C8064828","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q797280$3D305E95-39FB-4564-9F55-B49DF5F7D039","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3e9153bee99270c377a85f4160a70ed4b2686a1b","datavalue":{"value":"We present an algorithm to merge priority queues organized as heaps. The worst case number of comparisons required to merge two heaps of sizes k and n is \\(O(\\log(n)*\\log(k)).\\) The algorithm requires \\(O(k+\\log(n)*\\log(k))\\) data movements if heaps are implemented using arrays and \\(O(\\log(n)*\\log(k))\\) for a pointer-based implementation. Previous algorithms require either \\(O(n+K)\\) data movements and comparisons, or \\(O(k*\\log(\\log(n+k)))\\) comparisons and \\(O(k*\\log(n+k))\\) data movements. The algorithm presented in this paper improves on the previous algorithms for the case when \\(k>\\log(n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q797280$B42DC110-3495-416B-994C-F9FD66EC4C51","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797280$F3837C6A-1541-4452-92C3-10C37A51E92A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797280$7BCD8EF8-6C11-469D-A018-238B6016824E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76a0d1e041462ee9bc41a9b034310a50eb5d7b7b","datavalue":{"value":"3868604","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797280$B7F7356F-AB9E-4B3B-9A58-B482B0874147","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c2429349fe6ad34348df532161c2c6d4e44d116","datavalue":{"value":"merging","type":"string"},"datatype":"string"},"type":"statement","id":"Q797280$84B4DE58-3BEC-4A90-93D7-833B793ABBF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa4d2f1d74329489e48a80d23d6efcf7003116d1","datavalue":{"value":"priority queues","type":"string"},"datatype":"string"},"type":"statement","id":"Q797280$449EAF9D-8ED0-438D-A815-DF9187A3C119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4989eb152683ae59795f0e9b13db29659495b815","datavalue":{"value":"heaps","type":"string"},"datatype":"string"},"type":"statement","id":"Q797280$E3A31288-815B-423A-9EF8-8C933CCA8BF2","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f675d29867d5bc4f978d7817442b0447be62dcc9","datavalue":{"value":"Q62037536","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797280$C05165E7-8451-44BD-AC55-B6F1EA280F59","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":"Q797280$AE82CDBF-8D6C-47E9-BF49-BE35580F55FD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ce251c7788acaaa48f230e13016a87b9b0c6005c","datavalue":{"value":"https://doi.org/10.1007/bf00264229","type":"string"},"datatype":"url"},"type":"statement","id":"Q797280$3B906562-57E2-4F5B-87E4-D344DCE972FD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b4931eb869ab319ab4661fee9ecca7cdc385bdf2","datavalue":{"value":"W2518525525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797280$B71BF4CE-F3D3-4D0A-ABA6-76ADA90D39D9","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"2e37e8b656b0b48dd078d5a6a737b20493611511","datavalue":{"value":"journals/acta/SackS85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q797280$C9380304-5104-4429-AFAF-7CD33D605C40","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15c1979fb7b566db8a3c3495fe313b53d499694d","datavalue":{"value":{"entity-type":"item","numeric-id":3989853,"id":"Q3989853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab1d25f086f71ae2a27f1eda06e37ceb21a0e23c","datavalue":{"value":{"amount":"+0.8627443313598633","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":"Q797280$9163F972-92E2-41A8-B96E-E962C92BE97F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f62a2e6ced112b02b056f4debdc7eaf390adf6dd","datavalue":{"value":{"entity-type":"item","numeric-id":4019942,"id":"Q4019942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9d170e7103714756db6f50fbf8abdcf2c71f3c5","datavalue":{"value":{"amount":"+0.8590335249900818","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":"Q797280$D0BC0630-16D7-4029-AA18-C5D17F2612FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b1becb2c8d491e8566868b591863c459e465e82","datavalue":{"value":{"entity-type":"item","numeric-id":3026346,"id":"Q3026346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cea845e7a47f4247e2ccc4c1bd155dda8ccfaf30","datavalue":{"value":{"amount":"+0.8574761748313904","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":"Q797280$2CDD8710-23BD-41FB-8D6B-0E272BA017A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5accf8f4676fbf68d7d5c2ea00fd35ec28dda28a","datavalue":{"value":{"entity-type":"item","numeric-id":918196,"id":"Q918196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbd20777d4b31afeba496e7c1d9afe783e4c8db2","datavalue":{"value":{"amount":"+0.8494387865066528","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":"Q797280$A851D833-75E5-4238-9A61-09C9B96A40FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa5dd3e859d240cc5021b8e49782ad4d390b8c84","datavalue":{"value":{"entity-type":"item","numeric-id":689640,"id":"Q689640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aedfbd1c6aa070229f577897ba5786e7080829cf","datavalue":{"value":{"amount":"+0.8260586261749268","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":"Q797280$2209F7BC-DF54-4933-A577-EA711B912E74","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algorithm for merging heaps","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algorithm_for_merging_heaps"}}}}}