Hi.
There are two or three places in the Postgres source that implement heap
sort (e.g. tuplesort.c, nodeMergeAppend.c), and it's also needed by the
BDR code. It seemed reasonable to factor out the functionality.
I've attached a patch (binaryheap.diff) that contains a straightforward
implementation of a binary heap (originally written by Andres, with a
few bugfixes and cleanups by me).
There doesn't seem to be any place to put unit tests for code like this,
so at Alvaro's suggestion, I have attached a small standalone program I
used for testing (testbinheap.c) and a Makefile. If you copy them both
to src/backend/lib and run "make -f Makefile.binheap", it'll build the
test program. It's nothing exciting, just exercises the functions in
various ways.
I've also attached a patch (nodeMergeAppend.diff) that converts the code
in nodeMergeAppend.c to use binaryheap. It passes "make check", and also
the following test (which is planned as a merge append):
CREATE OR REPLACE VIEW gen AS SELECT * FROM
generate_series(1, 100000) g(i) ORDER BY g.i OFFSET 0;
SELECT * FROM (
SELECT * FROM gen UNION ALL SELECT * FROM gen UNION ALL
SELECT * FROM gen UNION ALL SELECT * FROM gen UNION ALL
SELECT * FROM gen UNION ALL SELECT * FROM gen) s
ORDER BY i OFFSET 1000000;
Initially there was a slight performance degradation with my patch, but
I speeded things up and now my code is at least at par with, and maybe
slightly faster than, the old code. On my laptop, both consistently
take ~2.4s on average to execute the above SELECT.
Comments? Suggestions?
-- Abhijit
diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 98ce3d7..327a1bc 100644
--- a/src/backend/lib/Makefile
+++ b/src/backend/lib/Makefile
@@ -12,6 +12,6 @@ subdir = src/backend/lib
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
-OBJS = ilist.o stringinfo.o
+OBJS = ilist.o binaryheap.o stringinfo.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h
new file mode 100644
index 0000000..aebf08f
--- /dev/null
+++ b/src/include/lib/binaryheap.h
@@ -0,0 +1,138 @@
+/*
+ * binaryheap.h
+ *
+ * A simple binary heap implementation
+ *
+ * Portions Copyright (c) 2012, PostgreSQL Global Development Group
+ *
+ * src/include/lib/binaryheap.h
+ */
+
+#ifndef BINARYHEAP_H
+#define BINARYHEAP_H
+
+/*
+ * This structure represents a single node in a binaryheap, and just
+ * holds two pointers. The heap management code doesn't care what is
+ * stored in a node (in particular, the key or value may be NULL),
+ * only that the comparator function can compare any two nodes.
+ */
+
+typedef struct binaryheap_node
+{
+ void *key;
+ void *value;
+} binaryheap_node;
+
+/*
+ * For a max-heap, the comparator must return:
+ * -1 iff a < b
+ * 0 iff a == b
+ * +1 iff a > b
+ * For a min-heap, the conditions are reversed.
+ */
+typedef int (*binaryheap_comparator)(binaryheap_node *a, binaryheap_node *b);
+
+/*
+ * binaryheap
+ *
+ * size how many nodes are currently in "nodes"
+ * space how many nodes can be stored in "nodes"
+ * comparator comparator to define the heap property
+ * nodes the first of a list of "space" nodes
+ */
+
+typedef struct binaryheap
+{
+ size_t size;
+ size_t space;
+ binaryheap_comparator compare;
+ binaryheap_node nodes[1];
+} binaryheap;
+
+/*
+ * binaryheap_allocate
+ *
+ * Returns a pointer to a newly-allocated heap that has the capacity to
+ * store the given number of nodes, with the heap property defined by
+ * the given comparator function.
+ */
+
+binaryheap *
+binaryheap_allocate(size_t capacity, binaryheap_comparator compare);
+
+/*
+ * binaryheap_free
+ *
+ * Releases memory used by the given binaryheap.
+ */
+
+void
+binaryheap_free(binaryheap *heap);
+
+/*
+ * binaryheap_add_unordered
+ *
+ * Adds the given key and value to the end of the heap's list of nodes
+ * in O(1) without preserving the heap property. This is a convenience
+ * to add elements quickly to a new heap. To obtain a valid heap, one
+ * must call binaryheap_build() afterwards.
+ */
+
+void
+binaryheap_add_unordered(binaryheap *heap, void *key, void *value);
+
+/*
+ * binaryheap_build
+ *
+ * Assembles a valid heap in O(n) from the nodes added by
+ * binaryheap_add_unordered(). Not needed otherwise.
+ */
+
+void
+binaryheap_build(binaryheap *heap);
+
+/*
+ * binaryheap_add
+ *
+ * Adds the given key and value to the heap in O(log n), while
+ * preserving the heap property.
+ */
+
+void
+binaryheap_add(binaryheap *heap, void *key, void *value);
+
+/*
+ * binaryheap_first
+ *
+ * Returns a pointer to the first (root, topmost) node in the heap
+ * without modifying the heap. Returns NULL if the heap is empty.
+ * Always O(1).
+ */
+
+binaryheap_node *
+binaryheap_first(binaryheap *heap);
+
+/*
+ * binaryheap_remove_first
+ *
+ * Removes the first (root, topmost) node in the heap and returns a
+ * pointer to it after rebalancing the heap. Returns NULL if the heap
+ * is empty. O(log n) worst case.
+ */
+
+binaryheap_node *
+binaryheap_remove_first(binaryheap *heap);
+
+/*
+ * binaryheap_replace_first
+ *
+ * Change the key and/or value of the first (root, topmost) node and
+ * ensure that the heap property is preserved. O(1) in the best case,
+ * or O(log n) if it must fall back to sifting the new node down.
+ */
+
+void
+binaryheap_replace_first(binaryheap *heap, void *newkey, void *newval);
+
+#endif /* BINARYHEAP_H */
diff --git a/src/backend/lib/binaryheap.c b/src/backend/lib/binaryheap.c
new file mode 100644
index 0000000..0fa8525
--- /dev/null
+++ b/src/backend/lib/binaryheap.c
@@ -0,0 +1,342 @@
+/*-------------------------------------------------------------------------
+ *
+ * binaryheap.c
+ * A simple binary heap implementaion
+ *
+ * Portions Copyright (c) 2012, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/backend/lib/binaryheap.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include <math.h>
+
+#include "lib/binaryheap.h"
+
+/* XXX
+ * The following is only to allow testbinheap.c to use this code outside
+ * the backend; should be removed before committing. */
+#ifdef TESTBINHEAP
+#define palloc malloc
+#define pfree free
+#endif
+
+static void sift_down(binaryheap *heap, size_t node_off);
+static void sift_up(binaryheap *heap, size_t node_off);
+static inline void swap_nodes(binaryheap *heap, size_t a, size_t b);
+
+/*
+ * binaryheap_allocate
+ *
+ * Returns a pointer to a newly-allocated heap that has the capacity to
+ * store the given number of nodes, with the heap property defined by
+ * the given comparator function.
+ */
+
+binaryheap *
+binaryheap_allocate(size_t capacity, binaryheap_comparator compare)
+{
+ int sz = sizeof(binaryheap) + sizeof(binaryheap_node) * (capacity-1);
+
+ binaryheap *heap = palloc(sz);
+ heap->compare = compare;
+ heap->space = capacity;
+ heap->size = 0;
+ return heap;
+}
+
+/*
+ * binaryheap_free
+ *
+ * Releases memory used by the given binaryheap.
+ */
+
+void
+binaryheap_free(binaryheap *heap)
+{
+ pfree(heap);
+}
+
+/*
+ * These utility functions return the offset of the left child, right
+ * child, and parent of the node at the given index, respectively.
+ *
+ * The heap is represented as an array of nodes, with the root node
+ * stored at index 0. The left child of node i is at index 2*i+1, and
+ * the right child at 2*i+2. The parent of node i is at index (i-1)/2.
+ */
+
+static inline int
+left_offset(size_t i)
+{
+ return 2 * i + 1;
+}
+
+static inline int
+right_offset(size_t i)
+{
+ return 2 * i + 2;
+}
+
+static inline int
+parent_offset(size_t i)
+{
+ return floor((i - 1) / 2);
+}
+
+/*
+ * binaryheap_add_unordered
+ *
+ * Adds the given key and value to the end of the heap's list of nodes
+ * in O(1) without preserving the heap property. This is a convenience
+ * to add elements quickly to a new heap. To obtain a valid heap, one
+ * must call binaryheap_build() afterwards.
+ */
+
+void
+binaryheap_add_unordered(binaryheap *heap, void *key, void *value)
+{
+ if (heap->size + 1 == heap->space)
+ Assert("binary heap is full");
+ heap->nodes[heap->size].key = key;
+ heap->nodes[heap->size++].value = value;
+}
+
+/*
+ * binaryheap_build
+ *
+ * Assembles a valid heap in O(n) from the nodes added by
+ * binaryheap_add_unordered(). Not needed otherwise.
+ */
+
+void
+binaryheap_build(binaryheap *heap)
+{
+ int i;
+
+ for (i = parent_offset(heap->size - 1); i >= 0; i--)
+ {
+ sift_down(heap, i);
+ }
+}
+
+/*
+ * binaryheap_add
+ *
+ * Adds the given key and value to the heap in O(log n), while
+ * preserving the heap property.
+ */
+
+void
+binaryheap_add(binaryheap *heap, void *key, void *value)
+{
+ binaryheap_add_unordered(heap, key, value);
+ sift_up(heap, heap->size - 1);
+}
+
+/*
+ * binaryheap_first
+ *
+ * Returns a pointer to the first (root, topmost) node in the heap
+ * without modifying the heap. Returns NULL if the heap is empty.
+ * Always O(1).
+ */
+
+binaryheap_node *
+binaryheap_first(binaryheap *heap)
+{
+ if (!heap->size)
+ return NULL;
+ return &heap->nodes[0];
+}
+
+/*
+ * binaryheap_remove_first
+ *
+ * Removes the first (root, topmost) node in the heap and returns a
+ * pointer to it after rebalancing the heap. Returns NULL if the heap
+ * is empty. O(log n) worst case.
+ */
+
+binaryheap_node *
+binaryheap_remove_first(binaryheap *heap)
+{
+ if (heap->size == 0)
+ return NULL;
+
+ if (heap->size == 1)
+ {
+ heap->size--;
+ return &heap->nodes[0];
+ }
+
+ /*
+ * Swap the root and last nodes, decrease the size of the heap (i.e.
+ * remove the former root node) and sift the new root node down to
+ * its correct position.
+ */
+
+ swap_nodes(heap, 0, heap->size - 1);
+
+ heap->size--;
+ sift_down(heap, 0);
+ return &heap->nodes[heap->size];
+}
+
+/*
+ * binaryheap_replace_first
+ *
+ * Change the key and/or value of the first (root, topmost) node and
+ * ensure that the heap property is preserved. O(1) in the best case,
+ * or O(log n) if it must fall back to sifting the new node down.
+ */
+
+void
+binaryheap_replace_first(binaryheap *heap, void *key, void *val)
+{
+ int ret;
+ size_t next_off = 0;
+
+ if (key)
+ heap->nodes[0].key = key;
+ if (val)
+ heap->nodes[0].value = val;
+
+ /*
+ * If the new root node is still larger than the largest of its
+ * children (of which there may be 0, 1, or 2), then the heap is
+ * still valid.
+ */
+
+ if (heap->size == 1) {
+ return;
+ }
+ if (heap->size == 2) {
+ next_off = 1;
+ }
+ else {
+ /* Two children: pick the larger one */
+ ret = heap->compare(&heap->nodes[2], &heap->nodes[1]);
+ if (ret == -1)
+ next_off = 1;
+ else
+ next_off = 2;
+ }
+
+ ret = heap->compare(&heap->nodes[next_off], &heap->nodes[0]);
+ if (ret == -1)
+ return;
+
+ /* The child is larger. Swap and sift the new node down. */
+
+ swap_nodes(heap, 0, next_off);
+ sift_down(heap, next_off);
+}
+
+/*
+ * Swap the contents of two nodes.
+ */
+
+static inline void
+swap_nodes(binaryheap *heap, size_t a, size_t b)
+{
+ binaryheap_node swap;
+ swap.value = heap->nodes[a].value;
+ swap.key = heap->nodes[a].key;
+
+ heap->nodes[a].value = heap->nodes[b].value;
+ heap->nodes[a].key = heap->nodes[b].key;
+
+ heap->nodes[b].key = swap.key;
+ heap->nodes[b].value = swap.value;
+}
+
+/*
+ * Sift a node up to the highest position it can hold according to the
+ * comparator.
+ */
+
+static void
+sift_up(binaryheap *heap, size_t node_off)
+{
+ /* manually unrolled tail recursion */
+ while (true)
+ {
+ size_t parent_off = parent_offset(node_off);
+
+ if (node_off == 0)
+ break;
+
+ if (heap->compare(&heap->nodes[parent_off],
+ &heap->nodes[node_off]) < 0)
+ {
+ /* heap property violated */
+ swap_nodes(heap, node_off, parent_off);
+
+ /* recurse */
+ node_off = parent_off;
+ }
+ else
+ break;
+ }
+}
+
+/*
+ * Sift a node down from its current position to satisfy the heap
+ * property.
+ */
+
+static void
+sift_down(binaryheap *heap, size_t node_off)
+{
+ /* manually unrolled tail recursion */
+ while (true)
+ {
+ size_t left_off = left_offset(node_off);
+ size_t right_off = right_offset(node_off);
+ size_t swap_off = 0;
+
+ /* Is the left child larger than the parent? */
+
+ if (left_off < heap->size &&
+ heap->compare(&heap->nodes[node_off],
+ &heap->nodes[left_off]) < 0)
+ {
+ swap_off = left_off;
+ }
+
+ /*
+ * If not (note: only one child can violate the heap property
+ * after a change), is the right child larger?
+ */
+
+ if (right_off < heap->size &&
+ heap->compare(&heap->nodes[node_off],
+ &heap->nodes[right_off]) < 0)
+ {
+ /* swap with the larger child */
+ if (!swap_off ||
+ heap->compare(&heap->nodes[left_off],
+ &heap->nodes[right_off]) < 0)
+ {
+ swap_off = right_off;
+ }
+ }
+
+ if (!swap_off)
+ {
+ /* heap condition fullfilled, abort */
+ break;
+ }
+
+ /* swap node with the child violating the property */
+ swap_nodes(heap, swap_off, node_off);
+
+ /* recurse, check child subtree */
+ node_off = swap_off;
+ }
+}
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index fec07b8..d4911bd 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1100,10 +1100,8 @@ typedef struct AppendState
* nkeys number of sort key columns
* sortkeys sort keys in SortSupport representation
* slots current output tuple of each subplan
- * heap heap of active tuples (represented as array indexes)
- * heap_size number of active heap entries
+ * heap heap of active tuples
* initialized true if we have fetched first tuple from each subplan
- * last_slot last subplan fetched from (which must be re-called)
* ----------------
*/
typedef struct MergeAppendState
@@ -1114,10 +1112,8 @@ typedef struct MergeAppendState
int ms_nkeys;
SortSupport ms_sortkeys; /* array of length ms_nkeys */
TupleTableSlot **ms_slots; /* array of length ms_nplans */
- int *ms_heap; /* array of length ms_nplans */
- int ms_heap_size; /* current active length of ms_heap[] */
+ struct binaryheap *ms_heap; /* binary heap of slot indices */
bool ms_initialized; /* are subplans started? */
- int ms_last_slot; /* last subplan slot we returned from */
} MergeAppendState;
/* ----------------
diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c
index d5141ba..6b2fef2 100644
--- a/src/backend/executor/nodeMergeAppend.c
+++ b/src/backend/executor/nodeMergeAppend.c
@@ -41,6 +41,8 @@
#include "executor/execdebug.h"
#include "executor/nodeMergeAppend.h"
+#include "lib/binaryheap.h"
+
/*
* It gets quite confusing having a heap array (indexed by integers) which
* contains integers which index into the slots array. These typedefs try to
@@ -49,9 +51,7 @@
typedef int SlotNumber;
typedef int HeapPosition;
-static void heap_insert_slot(MergeAppendState *node, SlotNumber new_slot);
-static void heap_siftup_slot(MergeAppendState *node);
-static int32 heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2);
+static int heap_compare_slots(binaryheap_node *a, binaryheap_node *b);
/* ----------------------------------------------------------------
@@ -88,7 +88,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
mergestate->ms_nplans = nplans;
mergestate->ms_slots = (TupleTableSlot **) palloc0(sizeof(TupleTableSlot *) * nplans);
- mergestate->ms_heap = (int *) palloc0(sizeof(int) * nplans);
+ mergestate->ms_heap = binaryheap_allocate(nplans, heap_compare_slots);
/*
* Miscellaneous initialization
@@ -143,9 +143,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
/*
* initialize to show we have not run the subplans yet
*/
- mergestate->ms_heap_size = 0;
mergestate->ms_initialized = false;
- mergestate->ms_last_slot = -1;
return mergestate;
}
@@ -160,6 +158,7 @@ TupleTableSlot *
ExecMergeAppend(MergeAppendState *node)
{
TupleTableSlot *result;
+ binaryheap_node *hn;
SlotNumber i;
if (!node->ms_initialized)
@@ -172,7 +171,9 @@ ExecMergeAppend(MergeAppendState *node)
{
node->ms_slots[i] = ExecProcNode(node->mergeplans[i]);
if (!TupIsNull(node->ms_slots[i]))
- heap_insert_slot(node, i);
+ {
+ binaryheap_add(node->ms_heap, node, (void *)i);
+ }
}
node->ms_initialized = true;
}
@@ -184,19 +185,22 @@ ExecMergeAppend(MergeAppendState *node)
* the logic a bit by doing this before returning from the prior call,
* but it's better to not pull tuples until necessary.)
*/
- i = node->ms_last_slot;
+ hn = binaryheap_first(node->ms_heap);
+ i = (int)hn->value;
node->ms_slots[i] = ExecProcNode(node->mergeplans[i]);
- if (!TupIsNull(node->ms_slots[i]))
- heap_insert_slot(node, i);
+ if (!TupIsNull(node->ms_slots[i])) {
+ binaryheap_replace_first(node->ms_heap, node, (void *)i);
+ }
+ else {
+ (void)binaryheap_remove_first(node->ms_heap);
+ }
}
- if (node->ms_heap_size > 0)
+ hn = binaryheap_first(node->ms_heap);
+ if (hn)
{
- /* Return the topmost heap node, and sift up the remaining nodes */
- i = node->ms_heap[0];
+ i = (int)hn->value;
result = node->ms_slots[i];
- node->ms_last_slot = i;
- heap_siftup_slot(node);
}
else
{
@@ -208,65 +212,15 @@ ExecMergeAppend(MergeAppendState *node)
}
/*
- * Insert a new slot into the heap. The slot must contain a valid tuple.
- */
-static void
-heap_insert_slot(MergeAppendState *node, SlotNumber new_slot)
-{
- SlotNumber *heap = node->ms_heap;
- HeapPosition j;
-
- Assert(!TupIsNull(node->ms_slots[new_slot]));
-
- j = node->ms_heap_size++; /* j is where the "hole" is */
- while (j > 0)
- {
- int i = (j - 1) / 2;
-
- if (heap_compare_slots(node, new_slot, node->ms_heap[i]) >= 0)
- break;
- heap[j] = heap[i];
- j = i;
- }
- heap[j] = new_slot;
-}
-
-/*
- * Delete the heap top (the slot in heap[0]), and sift up.
- */
-static void
-heap_siftup_slot(MergeAppendState *node)
-{
- SlotNumber *heap = node->ms_heap;
- HeapPosition i,
- n;
-
- if (--node->ms_heap_size <= 0)
- return;
- n = node->ms_heap_size; /* heap[n] needs to be reinserted */
- i = 0; /* i is where the "hole" is */
- for (;;)
- {
- int j = 2 * i + 1;
-
- if (j >= n)
- break;
- if (j + 1 < n && heap_compare_slots(node, heap[j], heap[j + 1]) > 0)
- j++;
- if (heap_compare_slots(node, heap[n], heap[j]) <= 0)
- break;
- heap[i] = heap[j];
- i = j;
- }
- heap[i] = heap[n];
-}
-
-/*
* Compare the tuples in the two given slots.
*/
static int32
-heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2)
+heap_compare_slots(binaryheap_node *a, binaryheap_node *b)
{
+ MergeAppendState *node = (MergeAppendState *)a->key;
+ SlotNumber slot1 = (int)a->value;
+ SlotNumber slot2 = (int)b->value;
+
TupleTableSlot *s1 = node->ms_slots[slot1];
TupleTableSlot *s2 = node->ms_slots[slot2];
int nkey;
@@ -291,7 +245,7 @@ heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2)
datum2, isNull2,
sortKey);
if (compare != 0)
- return compare;
+ return -compare;
}
return 0;
}
@@ -347,7 +301,5 @@ ExecReScanMergeAppend(MergeAppendState *node)
if (subnode->chgParam == NULL)
ExecReScan(subnode);
}
- node->ms_heap_size = 0;
node->ms_initialized = false;
- node->ms_last_slot = -1;
}
CFLAGS+=-Wall -g -I../../include -I../../include/lib -DTESTBINHEAP
testbinheap: binaryheap.o testbinheap.o
$(CC) binaryheap.o testbinheap.o -lm -o testbinheap
binaryheap.o: ../../include/lib/binaryheap.h binaryheap.c
testbinheap.o: ../../include/lib/binaryheap.h testbinheap.c
clean:
rm -f testbinheap testbinheap.o binaryheap.o
#include "c.h"
#include "binaryheap.h"
#include <stdio.h>
void print_heap(binaryheap *h);
int c(binaryheap_node *a, binaryheap_node *b)
{
/*
* The comparator could act on the nodes' keys too, but in this case
* it's easier to use the values.
*/
int av = *(int *)(a->value);
int bv = *(int *)(b->value);
if (av < bv)
return -1;
else if (av > bv)
return 1;
return 0;
}
int notc(binaryheap_node *a, binaryheap_node *b)
{
int av = *(int *)(a->value);
int bv = *(int *)(b->value);
if (av < bv)
return 1;
else if (av > bv)
return -1;
return 0;
}
int main()
{
binaryheap *h;
binaryheap_node *node;
int ints[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
h = binaryheap_allocate(7, c);
if (h->space != 7 || h->size != 0 || h->compare != c) {
printf("ERROR: binaryheap_allocate() is broken\n");
}
/*
* Does adding a bunch of elements to an empty heap result in a
* valid binary heap? If we remove them one by one, are they in
* the right order?
*/
binaryheap_add(h, "d", (void *)&ints[3]);
binaryheap_add(h, "b", (void *)&ints[1]);
binaryheap_add(h, "f", (void *)&ints[5]);
binaryheap_add(h, "a", (void *)&ints[0]);
binaryheap_add(h, "c", (void *)&ints[2]);
binaryheap_add(h, "e", (void *)&ints[4]);
binaryheap_add(h, "g", (void *)&ints[6]);
print_heap(h);
node = binaryheap_first(h);
printf("%d - ", *(int *)node->value);
while ((node = binaryheap_remove_first(h)) != NULL) {
printf("%d ", *(int *)node->value);
}
printf("\n");
binaryheap_free(h);
/*
* Does building a heap from unordered elements result in a valid
* binary heap? What if we add some more elements later?
*/
h = binaryheap_allocate(7, c);
binaryheap_add_unordered(h, "d", (void *)&ints[3]);
binaryheap_add_unordered(h, "b", (void *)&ints[1]);
binaryheap_add_unordered(h, "f", (void *)&ints[5]);
binaryheap_add_unordered(h, "a", (void *)&ints[0]);
binaryheap_build(h);
print_heap(h);
binaryheap_add(h, "c", (void *)&ints[2]);
binaryheap_add(h, "e", (void *)&ints[4]);
binaryheap_add(h, "g", (void *)&ints[6]);
print_heap(h);
node = binaryheap_first(h);
printf("%d - ", *(int *)node->value);
while ((node = binaryheap_remove_first(h)) != NULL) {
printf("%d ", *(int *)node->value);
}
printf("\n");
binaryheap_free(h);
/*
* Next, we add nodes 1..15 without regard to the heap property,
* assemble a valid heap from them, and remove elements from it
* one by one.
*/
int i = 0;
h = binaryheap_allocate(15, c);
while (i < 15) {
binaryheap_add_unordered(h, "", (void *)&ints[i]);
i++;
}
binaryheap_build(h);
print_heap(h);
node = binaryheap_first(h);
printf("%d - ", *(int *)node->value);
while ((node = binaryheap_remove_first(h)) != NULL) {
printf("%d ", *(int *)node->value);
}
printf("\n");
binaryheap_free(h);
/*
* Then we repeat the test above with a reversed comparator and the
* last few nodes added in after the heap is built, to make sure
* min-heaps work as expected.
*/
i = 0;
h = binaryheap_allocate(15, notc);
while (i < 12) {
binaryheap_add_unordered(h, "", (void *)&ints[14-i]);
i++;
}
binaryheap_build(h);
binaryheap_add(h, "", (void *)&ints[2]);
binaryheap_add(h, "", (void *)&ints[1]);
binaryheap_add(h, "", (void *)&ints[0]);
print_heap(h);
node = binaryheap_first(h);
printf("%d - ", *(int *)node->value);
while ((node = binaryheap_remove_first(h)) != NULL) {
printf("%d ", *(int *)node->value);
}
printf("\n");
binaryheap_free(h);
/*
* Now we test that replace_key works on a max heap.
*/
h = binaryheap_allocate(7, c);
binaryheap_add(h, "f", (void *)&ints[8]);
binaryheap_add(h, "d", (void *)&ints[6]);
binaryheap_add(h, "b", (void *)&ints[4]);
binaryheap_add(h, "g", (void *)&ints[9]);
binaryheap_add(h, "c", (void *)&ints[5]);
binaryheap_add(h, "a", (void *)&ints[3]);
binaryheap_add(h, "e", (void *)&ints[7]);
binaryheap_replace_first(h, "", (void *)&ints[10]);
binaryheap_replace_first(h, "", (void *)&ints[2]);
binaryheap_replace_first(h, "", (void *)&ints[11]);
binaryheap_replace_first(h, "", (void *)&ints[1]);
print_heap(h);
node = binaryheap_first(h);
printf("%d - ", *(int *)node->value);
while ((node = binaryheap_remove_first(h)) != NULL) {
printf("%d ", *(int *)node->value);
}
printf("\n");
binaryheap_free(h);
/*
* And again for a min-heap.
*/
h = binaryheap_allocate(7, notc);
binaryheap_add(h, "f", (void *)&ints[8]);
binaryheap_add(h, "d", (void *)&ints[6]);
binaryheap_add(h, "b", (void *)&ints[4]);
binaryheap_add(h, "g", (void *)&ints[9]);
binaryheap_add(h, "c", (void *)&ints[5]);
binaryheap_add(h, "a", (void *)&ints[3]);
binaryheap_add(h, "e", (void *)&ints[7]);
binaryheap_replace_first(h, "", (void *)&ints[1]);
binaryheap_replace_first(h, "", (void *)&ints[2]);
binaryheap_replace_first(h, "", (void *)&ints[11]);
binaryheap_replace_first(h, "", (void *)&ints[12]);
print_heap(h);
node = binaryheap_first(h);
printf("%d - ", *(int *)node->value);
while ((node = binaryheap_remove_first(h)) != NULL) {
printf("%d ", *(int *)node->value);
}
printf("\n");
binaryheap_free(h);
return 0;
}
/*
* The following functions recursively print a heap, with each node's
* contents represented as "idx=key/val" followed by its children. An
* empty heap is just "(empty)".
*/
void print_node(binaryheap *h, size_t node)
{
int l = node*2+1;
int r = node*2+2;
printf("(%d=%s/%d", node, (char *)h->nodes[node].key,
*(int *)h->nodes[node].value);
if (l < h->size) {
printf (" ");
print_node(h, node*2+1);
}
if (r < h->size) {
printf (", ");
print_node(h, node*2+2);
}
printf(")");
}
void print_heap(binaryheap *h)
{
if (h->size == 0) {
printf("(empty)\n");
return;
}
print_node(h, 0);
printf("\n");
}
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
