Inicio Explorar Axuda
Iniciar sesión
jonlandrum
/
search-heap
Seguir 1
Destacar 0
Fork 0
Ficheiros Incidencias 0 Pull Requests 0 Wiki

Sen descrición

Árbore: 305e9a4c94
Ramas Etiquetas
search-heap
ZIP TAR.GZ
Jonathan E. Landrum 305e9a4c94 Save State %!s(int64=8) %!d(string=hai) anos
.gitignore df58a5dfbc Initial commit. Adding the project to version control. %!s(int64=10) %!d(string=hai) anos
EmptyCollectionException.java df58a5dfbc Initial commit. Adding the project to version control. %!s(int64=10) %!d(string=hai) anos
IndexOutOfBoundsException.java 305e9a4c94 Save State %!s(int64=8) %!d(string=hai) anos
Main.java e2b1bcff5f Saving changes %!s(int64=10) %!d(string=hai) anos
NoSuchElementException.java df58a5dfbc Initial commit. Adding the project to version control. %!s(int64=10) %!d(string=hai) anos
Node.java 305e9a4c94 Save State %!s(int64=8) %!d(string=hai) anos
README.md 0960106b04 Update README.md %!s(int64=9) %!d(string=hai) anos
SearchHeap.java 305e9a4c94 Save State %!s(int64=8) %!d(string=hai) anos
UnknownErrorException.java 305e9a4c94 Save State %!s(int64=8) %!d(string=hai) anos
package.bluej 305e9a4c94 Save State %!s(int64=8) %!d(string=hai) anos

README.md

Search Heap

This is a data structure I am in the process of writing. As evidenced by the name, this structure is a well-ordered tree, thus it is also searchable. It is a type of heap that keeps both the global minimum and maximum in the root node, and also keeps the local minima and maxima in their respective subtree's root. This ensures O(1) search time for the extrema, and, because it is self-balancing, it guarantees O(lg n) search time for a given element, where n is the number of elements in the collection.

A zero-padded example with integers:

             (00, 13)
             /      \
    (01, 06)          (07, 12)
       / \               / \
(02, 03) (04, 05) (08, 09) (10, 11)