{"entities":{"Q578912":{"pageid":580679,"ns":120,"title":"Item:Q578912","lastrevid":62914872,"modified":"2026-04-11T08:58:23Z","type":"item","id":"Q578912","labels":{"en":{"language":"en","value":"Refined complexity analysis for heap operations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4014030"}},"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":"Q578912$41468DB5-9B1F-4273-A75F-F3CA146B7940","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"90fa24e37093abf03295e426ff093e5c47172edd","datavalue":{"value":{"text":"Refined complexity analysis for heap operations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q578912$37F6801D-7ADA-45F3-A573-2317E1C1676D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ea4da2a2b7c03cb692b5fee25cd55027f648a7e1","datavalue":{"value":"0624.68043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578912$B110AD90-5E0F-4CA6-9478-FCDD25415517","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"24aef36140858ece50c556b0ea76275f7f1ba1ec","datavalue":{"value":"10.1016/0022-0000(87)90016-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578912$7DAEDE0A-7C3F-4E45-9DD0-B72D419B2BC5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a4bb52e1c6671595e82831a75f140e5109329be","datavalue":{"value":{"entity-type":"item","numeric-id":578910,"id":"Q578910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578912$2C090A8A-3BB2-4607-BE9E-30DB4156274A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"225b84c8895960d56b44fcb1ab157d371a73efba","datavalue":{"value":{"entity-type":"item","numeric-id":578911,"id":"Q578911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578912$28F2E1BE-0CF9-45F3-AA00-6737F941ABA4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578912$1BAC5EBF-365F-4223-9838-B47C23F8873D","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":"Q578912$85815A8B-5412-4A60-85B5-2F079E6FC221","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9b4a1321b66a5a6c0cfa53d9f45ceb2b6f895467","datavalue":{"value":"A heap (priority queue) is a data structure for representing a set of items, each item having an associated numerical value, which facilitates such operations as insertion, deletion, merge (union), and findmin (find the item having the minimum value). It is well known that when n items are present the inherent complexity of these operations (in terms of comparisons) is log n per operation in the worst case. However, Cheriton and Tarjan have observed that when the frequency of findmin operations is small relative to the frequency of other operations, then certain implementations of heaps perform better than log n per operation. We explore this phenomenon with respect to inherent complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q578912$7850377F-33DE-4F5B-A7D9-98519B5637A3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578912$7F4991C0-BC5D-4EAB-B2D2-2643DD8D0A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578912$07229396-6899-4A44-8917-51168F583668","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"42e26465f1625769adde97016d50b3b98e3dc51e","datavalue":{"value":"4014030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578912$A9804C17-4FB8-4630-A14B-FDAF95AEA520","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a3e71e20fbe4cf516e0d9a07fc090360b67b372","datavalue":{"value":"heap","type":"string"},"datatype":"string"},"type":"statement","id":"Q578912$A47D0509-965E-42DA-9613-4227B973B317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"170f891b3a6d35c28ebb72165af585c2d5326a35","datavalue":{"value":"priority queue","type":"string"},"datatype":"string"},"type":"statement","id":"Q578912$D331D086-535D-420E-9EA9-107421CDE26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25bc710e4a99b4ad5c06b7d722ebbdb9259ca1e","datavalue":{"value":"data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q578912$D924BF12-ADA3-445B-8A36-CD9AA19CCE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9d001d34ac0a65e0ce02bc2a7ca653e2b21e5ce","datavalue":{"value":"inherent complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q578912$F3571B6C-ACAE-4808-8319-0DB82782F243","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b485fc4658020b1a7611168ffeb156f9b34eca33","datavalue":{"value":"frequency of findmin operations","type":"string"},"datatype":"string"},"type":"statement","id":"Q578912$ED1C217A-3DC7-45A0-8F3F-95DC18D359AD","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":"Q578912$DC51AA1F-F630-4DF4-B84F-E9C5C6130374","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578912$EF90D476-A715-4DFF-AE60-4B8982E0FF0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f50bb2463f68a38c17b8200f5931261dc0c5e7e","datavalue":{"value":{"entity-type":"item","numeric-id":4132283,"id":"Q4132283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578912$F65D6811-6F90-4974-AA52-D6F9A08D5658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578912$C635F5FB-625E-4B7D-9C92-3BED0921A866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc2e0d2db0a6d299eb21235fc0a97593259b0d3","datavalue":{"value":{"entity-type":"item","numeric-id":1394121,"id":"Q1394121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578912$DBCA133A-78BB-400B-8365-1588853639C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc40e90a7d9d6f368c35a80f35df70a6ff01287f","datavalue":{"value":{"entity-type":"item","numeric-id":4147586,"id":"Q4147586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578912$A9B6D43B-CE0F-4D5D-B873-CBDBDC2DE999","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"33a75b2aaf8d75883cca10750be8417fe8eb279b","datavalue":{"value":"https://doi.org/10.1016/0022-0000(87)90016-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q578912$FD194AD8-0E83-4B2F-804C-E97E6B1F4F34","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bf942fe2158457855ccba8ba33a9e41eab5ea8d3","datavalue":{"value":"W2011579772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578912$F8F0F1B9-9174-4482-B799-66380417838A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7284519a2077ed69dadcf4545c653ac92cf07cef","datavalue":{"value":{"entity-type":"item","numeric-id":3756520,"id":"Q3756520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8c001012fac012daf42f4bdc5fc33699a4f688a","datavalue":{"value":{"amount":"+0.8462001085281372","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":"Q578912$A0EAE478-9F74-400C-A8BC-872943D8561A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b198cc669ce21772c21c98151307e5aad4702e3","datavalue":{"value":{"entity-type":"item","numeric-id":2411045,"id":"Q2411045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6aad5284778e3e6f5c4e271e33a566e4b769eff3","datavalue":{"value":{"amount":"+0.8125126361846924","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":"Q578912$D34CE4FA-B42B-4020-A551-5A9CB34D501A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac6369d1905fc29a4e45e7a1e97dbf791af2c743","datavalue":{"value":{"entity-type":"item","numeric-id":4763425,"id":"Q4763425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"461ad6661e334f0010d3cb08419707408088b3a0","datavalue":{"value":{"amount":"+0.7986430525779724","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":"Q578912$5D338C9D-D25B-4B35-AC69-5D2383A99A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"143ba221aba20ad5d6cc8fed4894cf7fcd10b34e","datavalue":{"value":{"entity-type":"item","numeric-id":929299,"id":"Q929299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e05ea83b847403ac3a55f4b9e1550a325639ba2","datavalue":{"value":{"amount":"+0.7869939804077148","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":"Q578912$7FD4375D-C85F-4628-8B5B-2F61820FB548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c264f27745d5a462613312c91a59c265f7a80da","datavalue":{"value":{"entity-type":"item","numeric-id":5315373,"id":"Q5315373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d03a2e73aca4234936841fcab27f0977ac1fae85","datavalue":{"value":{"amount":"+0.7863903045654297","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":"Q578912$C540C7B2-FEE2-4415-AFC7-4D9C6D4AC145","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Refined complexity analysis for heap operations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Refined_complexity_analysis_for_heap_operations"}}}}}