Add functions to binaryheap for efficient key removal and update.
Previously, binaryheap didn't support updating a key and removing a
node in an efficient way. For example, in order to remove a node from
the binaryheap, the caller had to pass the node's position within the
array that the binaryheap internally has. Removing a node from the
binaryheap is done in O(log n) but searching for the key's position is
done in O(n).
This commit adds a hash table to binaryheap in order to track the
position of each nodes in the binaryheap. That way, by using newly
added functions such as binaryheap_update_up() etc., both updating a
key and removing a node can be done in O(1) on an average and O(log n)
in worst case. This is known as the indexed binary heap. The caller
can specify to use the indexed binaryheap by passing indexed = true.
The current code does not use the new indexing logic, but it will be
used by an upcoming patch.
Reviewed-by: Vignesh C, Peter Smith, Hayato Kuroda, Ajin Cherian,
Tomas Vondra, Shubham Khanna
Discussion: https://postgr.es/m/CAD21AoDffo37RC-eUuyHJKVEr017V2YYDLyn1xF_00ofptWbkg%40mail.gmail.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/b840508644151232b6ca1287dde617ed00ba2bdf
Modified Files
--------------
src/backend/executor/nodeGatherMerge.c | 1 +
src/backend/executor/nodeMergeAppend.c | 2 +-
src/backend/postmaster/pgarch.c | 3 +-
src/backend/replication/logical/reorderbuffer.c | 1 +
src/backend/storage/buffer/bufmgr.c | 1 +
src/bin/pg_dump/pg_backup_archiver.c | 1 +
src/bin/pg_dump/pg_dump_sort.c | 2 +-
src/common/binaryheap.c | 198 ++++++++++++++++++++++--
src/include/lib/binaryheap.h | 36 ++++-
src/tools/pgindent/typedefs.list | 1 +
10 files changed, 232 insertions(+), 14 deletions(-)