{"entities":{"Q7361857":{"pageid":31521110,"ns":120,"title":"Item:Q7361857","lastrevid":105423914,"modified":"2026-10-08T13:45:48Z","type":"item","id":"Q7361857","labels":{"en":{"language":"en","value":"Treaps"}},"descriptions":{"en":{"language":"en","value":"AFP entry Treaps"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5db80a8fb3c9d873751544965bd2425de93c34c","datavalue":{"value":"https://isa-afp.org/entries/Treaps.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361857$6B49AF71-402E-4AF3-896B-55B5BB782AF1","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e24c85cc74f22f9901f70520869c19fde2b00ac","datavalue":{"value":"Max W. Haslbeck","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361857$2647FAD4-257F-47C0-B644-C1D2CEAB330C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"85859c7ab42dcb8b36208f2902b7ce0d86423a6f","datavalue":{"value":"Manuel Eberl","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361857$7F60D159-D852-46C5-A580-298C10B197B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"78083bbf5b06a4f292e9e00ee445948e4fa51db5","datavalue":{"value":"Tobias Nipkow","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361857$179C408F-C9B1-43F5-B7E3-8513B2126797","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"30e362f4ecd47102c339b1ae19362d8b288ddaec","datavalue":{"value":"A Treap is a binary tree whose nodes contain pairs consisting of some payload and an associated priority. It must have the search-tree property w.r.t. the payloads and the heap property w.r.t. the priorities. Treaps are an interesting data structure that is related to binary search trees (BSTs) in the following way: if one forgets all the priorities of a treap, the resulting BST is exactly the same as if one had inserted the elements into an empty BST in order of ascending priority. This means that a treap behaves like a BST where we can pretend the elements were inserted in a different order from the one in which they were actually inserted. In particular, by choosing these priorities at random upon insertion of an element, we can pretend that we inserted the elements in random order , so that the shape of the resulting tree is that of a random BST no matter in what order we insert the elements. This is the main result of this formalisation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361857$8EC2E999-6EA0-4EFE-BA6F-49D4681083A0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"975193bacb8a76ff06ca8120b2a0330b2e6ef627","datavalue":{"value":{"entity-type":"item","numeric-id":5919010,"id":"Q5919010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$72D7A95B-135B-4EB0-9DA5-CD7E47F9FE2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31b73ce08d06d1b588784cb93b92e4db5b6ace8c","datavalue":{"value":{"entity-type":"item","numeric-id":1923861,"id":"Q1923861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$47888ADF-B21A-4532-9AC3-4B8C5471D5C0","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"9ac6eca1bc3d489b80eeaf5cfad7b175f5f00f3f","datavalue":{"value":{"entity-type":"item","numeric-id":7361878,"id":"Q7361878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$2AB4B92D-0393-4AEC-BBAB-81B1B5507DCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"2c009aab4f697160b25e89a5eefaab809089489d","datavalue":{"value":{"entity-type":"item","numeric-id":7361825,"id":"Q7361825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$218002FC-530C-4913-A30F-CF4CEF899A96","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a56c33c49680ed15bf9438494fe87a6286c086fc","datavalue":{"value":{"time":"+2018-02-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361857$0D2A2BEC-38F7-43BC-8072-FBB5D43E1B07","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e98503d74b466793d3d109420c857c76fea4b2c0","datavalue":{"value":{"text":"Treaps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361857$986559AD-A466-4A79-9C43-891303D97664","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$F287B422-832F-4D42-A62B-F806FE6958C5","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"ef7bddd24a035fe32f48fd95ea6033928a9b8e67","datavalue":{"value":{"entity-type":"item","numeric-id":7360788,"id":"Q7360788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$1A73163B-32AE-41D1-A473-883F6C0502AA","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$298F3274-0678-49F4-9C89-BCBA30F360D5","rank":"normal"}],"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"b0905d75219bb4493eac21af1641058f008c8307","datavalue":{"value":"28642","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361857$6BBBEDD9-86E1-4168-9405-9C17C8806F39","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361857$1EC7612D-5273-489C-926C-230163DE2E35","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$59DE6E0E-BD16-45F5-852B-4495E557106B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$4D3863A6-221B-4C06-A533-DA4744893B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"03281999c3208b8f3a62eaceadadf1ce834fe219","datavalue":{"value":{"entity-type":"item","numeric-id":12929,"id":"Q12929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$80DB9C06-3127-4D7A-ACD3-2EB2991A61DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"0777df209460f6d453f13a63edbbd60cf656f2b5","datavalue":{"value":{"entity-type":"item","numeric-id":40355,"id":"Q40355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$40EECDA8-1A97-4593-950D-1B2466E19C0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"74afd8a3b10bf054bf31ff15012404c74fd8d4f2","datavalue":{"value":{"entity-type":"item","numeric-id":53726,"id":"Q53726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$A584932D-E954-4EFE-A87D-CAFCD7FDA3D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"244ebbac6461f60bed6d50e50ce8194b0e233968","datavalue":{"value":{"entity-type":"item","numeric-id":40296,"id":"Q40296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$997F9AE8-5F7A-40E0-916F-C0E628F61746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"3a073d1e3162db58b1a890386d8dbe9eebb4637c","datavalue":{"value":{"entity-type":"item","numeric-id":40373,"id":"Q40373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$60575412-A6FE-460B-9D21-22EAAC60987E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"b74075817e632ca235b8b1333580f4f12e29f9fd","datavalue":{"value":{"entity-type":"item","numeric-id":40372,"id":"Q40372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$297EDBEA-0B07-4245-A7D7-8EDBC8FD69C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"868d665ea0607bf8bd28ea3e3872eb2ea87bd3d3","datavalue":{"value":{"entity-type":"item","numeric-id":40371,"id":"Q40371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$42905076-F379-43A3-AEB8-EBC46221E49B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"246d8bcd4bf1600a7c6d2b07f9f11f8689d33486","datavalue":{"value":{"entity-type":"item","numeric-id":40320,"id":"Q40320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$81880D33-F366-44CF-B3A3-F26F3B2AEB67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"6bbc316d4497e097d8fb3e48fd57f7643b44826c","datavalue":{"value":{"entity-type":"item","numeric-id":40246,"id":"Q40246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$F27A49FE-BFC8-4AC7-BDB0-582988BCA091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc41d9364226bfa8139f8dbc43b1b77967245f13","datavalue":{"value":{"entity-type":"item","numeric-id":17631,"id":"Q17631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$561F6BF5-3B30-4C85-BFFD-CC94DBB35B4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ecda3e6d8e971c0b93d4cf3afb41990e853f830f","datavalue":{"value":{"entity-type":"item","numeric-id":13212,"id":"Q13212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$E6C49797-C2C4-4EB6-B57C-47B2CE418050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"15196c2581266a184056ef1d8aed139d9f8df25d","datavalue":{"value":{"entity-type":"item","numeric-id":5975011,"id":"Q5975011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$8C1CD74B-E3B0-489A-A786-004E24401E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"139c69b2a23f419923a7989e28183ef8179b6836","datavalue":{"value":{"entity-type":"item","numeric-id":12833,"id":"Q12833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$A8EF49A1-3715-4C28-8691-39AC3D24B0FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"fb0918295880c75ce7e6107c7f8260e1eb005ccf","datavalue":{"value":{"entity-type":"item","numeric-id":40284,"id":"Q40284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$F8059249-2AB2-48F0-B824-765D7AAA7FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ce995af0d54f8ab3594278c155d6ae4d6e3a6165","datavalue":{"value":{"entity-type":"item","numeric-id":16614,"id":"Q16614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$C13805E7-162A-4CE5-927D-FD0700484DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"2ded5a481ece08049848bd1edb3f9afa21f0df2f","datavalue":{"value":{"entity-type":"item","numeric-id":16873,"id":"Q16873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$B1879189-A421-4AE4-9716-71D392A6DE12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bd0a78f92a43d7d4b9fb28d11c52d211df965f7e","datavalue":{"value":{"entity-type":"item","numeric-id":16053,"id":"Q16053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361857$FFBD2EB7-02B8-4955-B4BC-522F21EDC53A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Treaps (AFP entry Treaps)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Treaps_(AFP_entry_Treaps)"}}}}}