{"entities":{"Q2366561":{"pageid":2377304,"ns":120,"title":"Item:Q2366561","lastrevid":78604214,"modified":"2026-05-06T11:59:43Z","type":"item","id":"Q2366561","labels":{"en":{"language":"en","value":"An optimal algorithm for selection in a min-heap"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 227131"}},"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":"Q2366561$A6A7C9A3-C8EB-443B-97FA-31A0AE31E343","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8068bda9a7f25fe0f4654686a37a1976878b22a3","datavalue":{"value":{"text":"An optimal algorithm for selection in a min-heap","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366561$03E43BE8-0E88-4EA6-9161-B747C147DC02","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c141c675b0c5d9aed562f8bcef30a563f56b5c2b","datavalue":{"value":"0818.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366561$E0C41EE5-E281-4DFB-8934-A2E39ACC94DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e3d27020ae42071ce34c2e2b260b922db4110865","datavalue":{"value":{"entity-type":"item","numeric-id":215688,"id":"Q215688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366561$F0D58FC7-4E3E-49E9-A053-173F21C00EAD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366561$DE181A8C-4D7D-49CD-B37C-468475660858","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca925aef735ee73d86c6a323015bc1282d85f7d8","datavalue":{"value":{"time":"+1993-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366561$076B7403-44AC-494A-A798-761238852233","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e9410b0f727ca2a37774bf671909f65020e71f0c","datavalue":{"value":"The paper considers the problem of selecting the \\(k^{th}\\) smallest element in a min-heap of \\(n\\) elements (i.e., \\(x_ i > x_{\\lfloor i/2 \\rfloor}\\) holds for \\(i = 1, \\dots, n)\\) when \\(n \\gg k\\). It is shown that this is possible in \\({\\mathcal O} (k)\\) time. The technique used is rather interesting in itself: clusters (called clans) are formed incrementally; forming clans means partitioning the heap into groups of \\(\\lfloor \\log k \\rfloor\\) elements such that the first clan contains the first \\(\\lfloor \\log k \\rfloor\\) elements, the second clan contains the next \\(\\lfloor \\log k \\rfloor\\) elements, etc. The largest elements of a clan are maintained in an auxiliary heap. This construction leads to a \\({\\mathcal O} (k \\log \\log k)\\) algorithm which is refined in a sequence of steps yielding the main result of this paper. Two applications are discussed in the Introduction: selecting the \\(k\\) smallest spanning trees of a weighted undirected graph, and a resource allocation problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366561$950458B0-34ED-4395-8697-388A0F529BC0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366561$F93997F0-A751-4F15-8B47-D203D447B74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366561$609D011C-778C-4118-9271-507CD516640E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3dfbf3fdbf03a2ff60d1de87e380c1ba3fe42e3","datavalue":{"value":"227131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366561$2B78F96F-935C-487E-8896-04F298F8A601","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea3d9213df409c20757f433fc292fa0744a379c7","datavalue":{"value":"implicit data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366561$1C57E3C5-6920-4089-BB0F-449DF1D8BBC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6c1af2e9f24e8ae2db51afd63b9603bb4fa4f16","datavalue":{"value":"\\(k^{th}\\) smallest element","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366561$FC83F1ED-227B-4467-95BA-ACD2F6161D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82bc52c36ef007d1d7de745be58c15fbc8cb39fa","datavalue":{"value":"min-heap","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366561$C955D06C-8D25-4B92-8343-BCE80F08E8D8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8fabcf9d0a5f9cced75f459bc47f13668ccf8315","datavalue":{"value":"Q56049346","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366561$7070DCA5-1888-479B-B5EB-C85776C4D2BB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b55806ac3006ec2d3bb3cf03b6c3b09dbfabbcd2","datavalue":{"value":{"entity-type":"item","numeric-id":406466,"id":"Q406466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366561$0212B5CD-97E6-430C-8F0A-F2320459C4D6","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":"Q2366561$57E348B1-0964-4DF5-A4A8-E0946D37149D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5ceb81163c7961076589c2c768fa1a9ed91338ad","datavalue":{"value":"https://doi.org/10.1006/inco.1993.1030","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366561$1D0CC27D-DC77-4AB1-8BEF-C0B213FD4A0A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d08e566d4c66d2674a00586f01c1b9df7164fff0","datavalue":{"value":"W2111340560","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366561$3DDA7930-B69D-4849-B415-A9C0A4808EDD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"33a9218670330fe47205867cab2a58ccb032c573","datavalue":{"value":"10.1006/INCO.1993.1030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366561$D864D787-7CAE-472F-9918-508518BD64AC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77295ad8d9c0be44643b4fcf03bded1419e62fd4","datavalue":{"value":{"entity-type":"item","numeric-id":4228284,"id":"Q4228284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd68472ff28d74425adcdb4c0734dbe7199d7409","datavalue":{"value":{"amount":"+0.8085033893585205","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":"Q2366561$1ABE2B12-E2EB-49E9-BBD0-E12C3014EC30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0b8689e5292e61e88973a3f6c0482216e2d4adb","datavalue":{"value":{"entity-type":"item","numeric-id":4028913,"id":"Q4028913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94d3256dd76c169d2b2e39602792278a109ecb35","datavalue":{"value":{"amount":"+0.8043718338012695","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":"Q2366561$E9424693-64FD-42F3-B10B-53C2FAC82EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c2d05e8c079e4169650ad57d2aacd2dd25a05cd","datavalue":{"value":{"entity-type":"item","numeric-id":5919538,"id":"Q5919538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"526cd57172dc7360226d9ec5df0a77b0e2b5129b","datavalue":{"value":{"amount":"+0.7822601795196533","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":"Q2366561$C5928171-E635-4D1C-803E-3CA3932FB9DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal algorithm for selection in a min-heap","badges":[]}}}}}