So, it is a tree with regard to the keys and a heap with regard to the priorities.
To delete a key, make its weight infinite and rotate it down the tree (again, in heap order) until it becomes a leaf, and then remove it. To insert a new key, generate the priority and do a regular BST insertion, and then rotate it up the tree (to maintain the heap). We get randomized heap priorities by making sure we assign these randomly (one way is by hashing the keys themselves). So now, the tree’s structure (shape) will depend entirely on the randomized weight we gave the heap values. To make that second key a little more useful for us, use a random heap weight. There is only one arrangement for this treap regardless of the order by which elements were picked to construct the tree (try it!). Now, here’s the magical property about treap data structure. The numbers indicate the heap arrangement of the data structure (arranged in max-heap order), and the alphabets indicate the tree part of things (left child < parent <= right child). Therefore, we introduce another key (See picture). However, if done with a single element, it will look like a line (because in the BST, the left child must be less than its parent and the right child must be greater than or equal to its parent, but for a heap, each parent should either be all bigger than its children or all smaller than its children). When we construct a heap, we basically build an ordered binary tree AND make it satisfy the “heap” property. Heaps can be logically stored in arrays, which is a bonus (random access times).Ī treap data structure combines the best of both heaps and binary search trees. This property is why it makes a nice data structure to implement priority queues (if we remove one element, we need to choose from 2 children to find out who takes the removed elements’ place). (A max-heap is basically when all parents in the tree have keys of greater values than or equal to its children’s keys). Heaps are basically just a binary tree with a “heap” property. All these add complexity to the algorithm at the pretext of offering the advantages of a normal BST. These were combined with some optimizations – e.g., the splay trees move the more accessed elements closer to the top and rebalances – B–trees store more information per node than just one element. Therefore, we need to rebalance that tree (which takes O(n) time for a tree containing n elements).įor a while, computer scientists used balanced search trees, which incorporated rotation algorithms to keep it balanced after adding and removing nodes – like red–black trees, splay trees, AVL trees, etc.
Binary Search Treesĭeletions and additions of nodes can make the tree unbalanced (heavier on sides therefore, the property we value about BSTs, the ability to distribute data by equal divisions, goes out of whack). A Treap data structure is basically a combination of a binary search tree and a heap.