{"entities":{"Q40356":{"pageid":40412,"ns":120,"title":"Item:Q40356","lastrevid":105426287,"modified":"2026-10-09T10:05:04Z","type":"item","id":"Q40356","labels":{"en":{"language":"en","value":"Treaps"}},"descriptions":{"en":{"language":"en","value":"AFP entry Treaps"}},"aliases":{},"claims":{"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"b0905d75219bb4493eac21af1641058f008c8307","datavalue":{"value":"28642","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40356$55D7DBEE-69B2-4F0A-8F0E-8945CC6B8379","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":"Q40356$0B0A0E7A-F89D-4CBA-BBF8-E81CF6A7DD09","rank":"normal"}],"P29":[{"mainsnak":{"snaktype":"value","property":"P29","hash":"0089121a97d2a26db565eb13a2cab566d317d04d","datavalue":{"value":"https://www.isa-afp.org/entries/Treaps.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40356$40646CC4-1142-4136-8A97-F5CD8D6B5BBA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40356$25FFA78E-ECA3-4782-A444-6544465DF53E","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":"Q40356$98CF00D2-AF97-4FD8-BE70-846BAE56B9B4","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":"Q40356$5A357DDC-1655-4D0D-A230-14724303DE86","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":"Q40356$1515634B-2BAB-4153-80B3-4BF6AADF159F","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":"Q40356$EBB95A46-9C72-43DB-A7CA-30FA0200FA51","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":"Q40356$40C0D701-4002-4322-829E-0B7A0DBB486F","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":"Q40356$BF9FD671-2CA1-4D73-9E46-6396FF74D4C7","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":"Q40356$AAD30609-BFBD-4892-AC0F-0E014F767A53","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":"Q40356$FD149E8C-EDA2-430B-ABF3-CC1A15738862","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":"Q40356$41040569-B026-4AF0-B8B2-44CF620EAC3B","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":"Q40356$819BD360-DB84-4000-8C05-3F5CBFC664F0","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":"Q40356$1FD1CCE3-DEE1-4074-9537-8F59602F3524","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":"Q40356$F58281A9-985D-456F-8ECF-D7BB04E2942E","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":"Q40356$6C41A1CB-F5B3-4967-883C-22EFD9369979","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":"Q40356$848D91A3-244D-4659-91FD-342122718D61","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":"Q40356$B3CD1A7F-536F-44FB-932D-DDC0E6DF495D","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":"Q40356$5750FE18-9972-4BEA-96A5-3DE7B085C040","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":"Q40356$4123B35C-CD21-4466-A325-80EBE108D2C9","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":"Q40356$EDBD8576-6CD7-497D-A51B-8D8B35239A0F","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":"Q40356$240F0BC3-815F-41FB-A27A-78C2E95549C5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5db80a8fb3c9d873751544965bd2425de93c34c","datavalue":{"value":"https://isa-afp.org/entries/Treaps.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40356$36844125-1E20-45FF-969F-53A3728DAE81","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e24c85cc74f22f9901f70520869c19fde2b00ac","datavalue":{"value":"Max W. Haslbeck","type":"string"},"datatype":"string"},"type":"statement","id":"Q40356$E74CAEF7-6A51-4844-AC73-BC074B6E67B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"85859c7ab42dcb8b36208f2902b7ce0d86423a6f","datavalue":{"value":"Manuel Eberl","type":"string"},"datatype":"string"},"type":"statement","id":"Q40356$D280C4A0-6F6D-4C8B-B079-94198A491751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"78083bbf5b06a4f292e9e00ee445948e4fa51db5","datavalue":{"value":"Tobias Nipkow","type":"string"},"datatype":"string"},"type":"statement","id":"Q40356$F107546E-1537-47AA-ACD6-73840119B062","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":"Q40356$AB8A37D2-A352-4F1B-B3D8-49BE3E58AD8E","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":"Q40356$8D378E32-0192-41A3-B7B4-684A864BC1AF","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":"Q40356$8A86EE9A-BC64-49DB-A83F-C590631E3AD2","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":"Q40356$2976BD8C-3781-4D2D-9990-B146CC8C10DF","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":"Q40356$1268460E-0B59-474F-8FB1-71AC8E52B8D3","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":"Q40356$F29381AC-2E2D-4662-A658-64919115BE7B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e98503d74b466793d3d109420c857c76fea4b2c0","datavalue":{"value":{"text":"Treaps","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q40356$4A337DE2-A3FA-462D-8AAF-37B2F7D0975F","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":"Q40356$A17FE6DF-528C-45D0-BC41-DD3DD8929851","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":"Q40356$4185C7BF-6BB1-4227-A618-3043C105088D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Treaps","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Treaps"}}}}}