Priority Search Tree Demo
A priority search tree is a data structure that allows for efficient
searching and point location in one and one-half dimensions (the upper
bound on Y is missing). It is a hybrid of a heap and a balanced
search tree (heap for y-coordinates, search tree for x-coordinates).
The applet below (my final project for
Computational Geometry)
demonstrates the data structure and algorithm
described by Edward McCreight in his 1985 paper Priority Search
Trees. For more information on priority search
trees, read the lectures Priority Search
Trees (Scribe: Dina Q Goldin Karon) and Dynamic Priority Search Trees (Scribe:
Mike Shapiro). There's also a good paper entitled
Tutorial on Priority
Search Trees by Wen-Chun Ni.
