Efficient Running Median using an Indexable Skiplist (Python)
Efficient Running Median using an Indexable Skiplist « Python recipes « ActiveState Code
Python版のSkipList実装ということで参考にします。
まだ試してないですがぱっと見た限りだとシリアライズ系処理(pickle/unpickle)を行いたい場合は実装の拡張が必要そうですね。そうだとした場合修正版はどこかで公開してもよいかも。
Java版はBlogopolisで有名な浜本階生さんが公開されているんですね。
要素の挿入、削除、ランダムアクセスが全部高速なリストを作った - kaisehのブログ