CODEWITHSUNDEEP
algorithmdata-structuresheapbinary-search-tree
saeedn
saeedn

Reputation: 3378

A balanced binary search tree which is also a heap

I'm looking for a data structure where each element in it has two keys. With one of them the structure is a BST and looking at the other one, data structure is a heap. With a little search, I found a structure called Treap. It uses the heap property with a random distribution on heap keys to make the BST balanced!

What I want is a Balanced BST, which can be also a heap. The BST in Treap could be unbalanced if I insert elements with heap Key in the order of my choice.

Is there such a data structure?

Upvotes: 2

Views: 1227

Answers (1)

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

Priority Search Tree is the structure which is both a Balanced BST and a Heap. For details see this paper or this book: "Handbook of Data Structures and Applications" (Chapter 18.5).

This structure can be used to efficiently search elements that have minimal of all the "heap" keys and "BST" keys in given range.

Upvotes: 1

Related Questions