Order statistic tree based on Treap data structure and
powerful Implicit Treap for interval operations.
Compact ObjectPascal generic class TTreapNode and generic class TImplicitTreapNode.
See Wiki for more info.
Why another treap implementation? The story begins from the SPOJ problem ALLIN1.
All accepted solutions was in C/C++ and one in D-DMD. I asked myself - why not Pascal?
My first attempt was based on records (mode DELPHI) - time 2.28s.
After reading Michalis Kamburelis excellent Modern Object Pascal Introduction for Programmers I started ftreap.
So, here we are.
Here some testing results on IDEONE.
| Method \ Number of keys | 100000 | 200000 | 400000 | 800000 | 1600000 |
|---|---|---|---|---|---|
| Insert | 0.08s | 0.19s | 0.42s | 1.06s | 2.58s |
FTREAP vs FCL-STL gset.
- Lazarus - The professional Free Pascal RAD IDE.
- PasDoc - Documentation tool for ObjectPascal (Free Pascal, Lazarus, Delphi).
This project is licensed under the MIT License - see the LICENSE file for details.