Resources for file descriptors and memory blocks.

[libucw.git] / ucw / heap.h

diff --git a/ucw/heap.h b/ucw/heap.h
index d8ef8d5c97cd7a6f1829917c8aa4c87a8bb94e3b..e0a33b02a60968bd5e0d24003c7b43a3b59c6cfe 100644 (file)
--- a/ucw/heap.h
+++ b/ucw/heap.h
@@ -98,7 +98,7 @@
   } while(0)
 
 /**
   } while(0)
 
 /**

- * Insert `heap[num + 1]` in `O(log(n))` time.
+ * Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before.

  **/
 #define HEAP_INSERT(type,heap,num,less,swap)                                           \
   do {                                                                                 \
  **/
 #define HEAP_INSERT(type,heap,num,less,swap)                                           \
   do {                                                                                 \


@@ -121,6 +121,19 @@
     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                            \
   } while(0)
 
     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                            \
   } while(0)
 

+/**
+ * If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
+ * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
+ * The time complexity is `O(log(n))`.
+ **/
+#define HEAP_DECREASE(type,heap,num,less,swap,pos)                                     \
+  do {                                                                                 \
+    uns _j, _u;                                                                                \
+    type x;                                                                            \
+    _j = pos;                                                                          \
+    HEAP_BUBBLE_UP_J(heap,num,less,swap);                                              \
+  } while(0)
+

 /**
  * Delete `heap[pos]` in `O(log(n))` time.
  **/
 /**
  * Delete `heap[pos]` in `O(log(n))` time.
  **/