{"entities":{"Q1108784":{"pageid":1119533,"ns":120,"title":"Item:Q1108784","lastrevid":66731004,"modified":"2026-04-12T12:29:42Z","type":"item","id":"Q1108784","labels":{"en":{"language":"en","value":"On the random construction of heaps"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068256"}},"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":"Q1108784$5668ADDB-FF54-47F5-B95B-29254C018EF8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6550f04aeeb5301097f9f85ea3d2840cf44751b1","datavalue":{"value":{"text":"On the random construction of heaps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108784$0B69B10C-86B7-4676-A799-6FF3EAF2FFF1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"41856b8665b21d5a97583421d9206e70f206d17a","datavalue":{"value":"0654.68026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108784$23196854-57EF-4B59-AAAC-33A0BDD1A4C3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2f8d27fcea810e26abdcf1c96cc3f990bdde2b9c","datavalue":{"value":"10.1016/0020-0190(88)90101-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108784$90B6F3DC-501B-4EBE-9344-440A5C8FDF7F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108784$439E1651-0739-42C2-8BA3-663377681F85","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1108784$613E669C-E706-41A2-AE0E-75D72B5CDD62","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b00361bfebe5373cc8ec13c924fffe12f59b12f7","datavalue":{"value":"We give a simple proof of the result of \\textit{B. Bollob\u00e1s} and \\textit{I. Simon} [J. Algorithms 6, 466-477 (1985; Zbl 0592.68022)] on the linear expected time construction of a binary heap. We also give bounds on the probability that the construction time is much more than this and generalize the result to d-heaps, \\(d\\geq 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108784$9E7F9906-4579-4E52-B440-85F33E325438","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108784$3D9800CE-490A-40B4-8AB4-7E3922FEE689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108784$7929CFB3-547E-46FF-8806-133827E03826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108784$9278A1DF-BFB2-417E-A37B-D8D64E771BCD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"146c47e975ef9d271040422e098867940fcd3e18","datavalue":{"value":"4068256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108784$F1629982-2A0B-4836-A7B6-BF8588D1A418","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108784$D14F1196-BD84-4831-98BC-53F18C90F426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ca33292eb14a285791751163b362edd3de41d2b","datavalue":{"value":"binary heap","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108784$F498BBBA-C488-4E20-BEC9-59083DCFD748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f07464f12b1a6190df89775f6e0d52060cfd7102","datavalue":{"value":"d-heaps","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108784$A189E31D-ABD8-4A61-BA94-D0D8FF6BE8CA","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d9c0255b7d251dbf80f751ffdbd0dc51a8e4d991","datavalue":{"value":"Q57401618","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108784$06EFBC4D-A76B-47A6-9B6E-8423EC54DD48","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108784$6E04073D-F9E1-4CB1-A1B8-283AA96DAF40","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":"Q1108784$9E232559-A11A-4B75-BD7A-53170178CF47","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f9926b5abfa5864464e13a58dd2e2319149b4726","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90101-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108784$A9D4E2AC-B848-4791-B806-A6490FB4823C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"31227479282d457697a3e3d034b2bb5e28e2cc91","datavalue":{"value":"W1984625335","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108784$AF4D42DB-0292-446D-A92A-38A573CC430E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a5bfecbd86a7ba8cbea6d428d72d3bcb46bfe0a","datavalue":{"value":{"entity-type":"item","numeric-id":3721798,"id":"Q3721798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108784$24B9E308-05D0-49F3-8BE9-F8D8BF2BBD75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108784$D7365D7D-FE18-4759-A243-69DD1AC1A670","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":"Q1108784$CD4FB787-52E7-41E4-861D-BB0FAA9F40B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0a738d7bef8ab818e824bcf35d76a22e769d1d8","datavalue":{"value":{"entity-type":"item","numeric-id":4730782,"id":"Q4730782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0118cc5e3b072c9d315b868d839e3260d7ade3e6","datavalue":{"value":{"amount":"+0.8223475813865662","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":"Q1108784$A9A6EB06-B7AE-4048-90D6-03D5C2929BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0379be09f13422fba37579811e00f46b54990ca3","datavalue":{"value":{"entity-type":"item","numeric-id":4428915,"id":"Q4428915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19147bf396add2159ffb48e1b574c44f1f24831c","datavalue":{"value":{"amount":"+0.8010864853858948","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":"Q1108784$0B8535A8-9144-4DFC-B621-A19ED27103FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc11a2443226ac585a31058514805ee3482c807f","datavalue":{"value":{"entity-type":"item","numeric-id":3201759,"id":"Q3201759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b57846ae6c6344e3820ade3576b365a64ffb84d2","datavalue":{"value":{"amount":"+0.791389524936676","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":"Q1108784$4915AD8E-D539-42AD-8603-412F7C4AC046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"feca15e65481329ee857778a288ba2ed33fff624","datavalue":{"value":{"entity-type":"item","numeric-id":3718164,"id":"Q3718164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61849ff4f64e6faec9bd7804e2ab40b8d41684e5","datavalue":{"value":{"amount":"+0.7905365824699402","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":"Q1108784$9FF203D0-D032-4287-A70C-AFF75A425104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bb22f499d7ef7df44ac8201c7b79095662a458b","datavalue":{"value":{"entity-type":"item","numeric-id":6487971,"id":"Q6487971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3aa011e57ba477425a00ed80fae24cd5e39ea232","datavalue":{"value":{"amount":"+0.7843236327171326","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":"Q1108784$C6229265-1ED7-4A0D-B7D2-ADC1F78D9F1A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the random construction of heaps","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_random_construction_of_heaps"}}}}}