[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/heap 151a314 17/31: Added heap-merge function for mergi
From: |
Stefan Monnier |
Subject: |
[elpa] externals/heap 151a314 17/31: Added heap-merge function for merging heaps. |
Date: |
Mon, 14 Dec 2020 12:13:36 -0500 (EST) |
branch: externals/heap
commit 151a3142faafccc05bcc030c41a1a7e0f398e6da
Author: Toby S. Cubitt <toby-predictive@dr-qubit.org>
Commit: Toby S. Cubitt <toby-predictive@dr-qubit.org>
Added heap-merge function for merging heaps.
(Not very efficient for binary heaps, only O(n).)
---
heap.el | 66 ++++++++++++++++++++++++++++++++++++++++-------------------------
1 file changed, 41 insertions(+), 25 deletions(-)
diff --git a/heap.el b/heap.el
index 403342d..81fef88 100644
--- a/heap.el
+++ b/heap.el
@@ -69,6 +69,8 @@
;; * increased default heap size to 16, and default resize-factor to 2
;; * added `heap-build' function for efficiently building a heap out of
;; a vector
+;; * added `heap-merge' function for merging heaps (not very efficient
+;; for binary -- or ternary -- heaps, only O(n))
;;
;; Version 0.2.2
;; * fixed bug in `heap-copy'
@@ -199,31 +201,6 @@ defaulting to 2."
(heap--create compare-function initial-size resize-factor))
-(defun heap-build (compare-function vec &optional resize-factor)
- "Build a heap from vector VEC with COMPARE-FUNCTION
-as the comparison function.
-
-Note that VEC is modified, and becomes part of the heap data
-structure. If you don't want this, copy the vector first and pass
-the copy in VEC.
-
-COMPARE-FUNCTION takes two arguments, A and B, and returns
-non-nil or nil. To implement a max-heap, it should return non-nil
-if A is greater than B. To implemenet a min-heap, it should
-return non-nil if A is less than B.
-
-RESIZE-FACTOR sets the factor by which the heap's size is
-increased if it runs out of space, defaulting to 2."
- (or resize-factor (setq resize-factor 2))
- (let ((heap (heap--create compare-function (length vec) resize-factor))
- (i (ceiling (1- (expt 3
- (ceiling (1- (log (1+ (* 2 (length vec))) 3))))) 2)))
- (setf (heap--vect heap) vec
- (heap--count heap) (length vec))
- (while (>= (decf i) 0) (heap--sift-down heap i))
- heap))
-
-
(defun heap-copy (heap)
"Return a copy of heap HEAP."
(let ((newheap (heap--create (heap--cmpfun heap) (heap--size heap)
@@ -322,6 +299,45 @@ Note that only the match highest up the heap is modified."
nil))) ; return nil if no match was found
+(defun heap-build (compare-function vec &optional resize-factor)
+ "Build a heap from vector VEC with COMPARE-FUNCTION
+as the comparison function.
+
+Note that VEC is modified, and becomes part of the heap data
+structure. If you don't want this, copy the vector first and pass
+the copy in VEC.
+
+COMPARE-FUNCTION takes two arguments, A and B, and returns
+non-nil or nil. To implement a max-heap, it should return non-nil
+if A is greater than B. To implemenet a min-heap, it should
+return non-nil if A is less than B.
+
+RESIZE-FACTOR sets the factor by which the heap's size is
+increased if it runs out of space, defaulting to 2."
+ (or resize-factor (setq resize-factor 2))
+ (let ((heap (heap--create compare-function (length vec) resize-factor))
+ (i (ceiling (1- (expt 3
+ (ceiling (1- (log (1+ (* 2 (length vec))) 3))))) 2)))
+ (setf (heap--vect heap) vec
+ (heap--count heap) (length vec))
+ (while (>= (decf i) 0) (heap--sift-down heap i))
+ heap))
+
+
+(defun heap-merge (heap &rest heaps)
+ "Merge HEAP with remaining HEAPS.
+
+The merged heap takes the comparison function and resize-fector
+of the first HEAP argument.
+
+\(Note that in this heap implementation, the merge operation is
+not very efficient, taking O(n) time for combined heap size n\)."
+ (setq heaps (mapcar 'heap--vect heaps))
+ (heap-build (heap--cmpfun heap)
+ (apply 'vconcat (heap--vect heap) heaps)
+ (heap--resize heap)))
+
+
(provide 'heap)
- [elpa] externals/heap 5ad96c3 14/31: Updated Package-Version, Package-Requires, and Keywords package headers., (continued)
- [elpa] externals/heap 5ad96c3 14/31: Updated Package-Version, Package-Requires, and Keywords package headers., Stefan Monnier, 2020/12/14
- [elpa] externals/heap 11738aa 12/31: Re-filled to 72 chars/line, for mailing to gnu-emacs-sources list, Stefan Monnier, 2020/12/14
- [elpa] externals/heap 596261c 28/31: Implement iterator generators on collection data structures., Stefan Monnier, 2020/12/14
- [elpa] externals/heap 32e75bb 31/31: * heap.el: Fix first line format, Stefan Monnier, 2020/12/14
- [elpa] externals/heap 8a40ef4 08/31: Version 0.12.1 of the predictive completion package., Stefan Monnier, 2020/12/14
- [elpa] externals/heap 8ece2ad 24/31: Enable lexical binding, and fix issues it picks up., Stefan Monnier, 2020/12/14
- [elpa] externals/heap aa998ae 20/31: Updated copyright attribution and license (GPL2 -> GPL3)., Stefan Monnier, 2020/12/14
- [elpa] externals/heap 778a848 26/31: Bump version numbers and copyright years., Stefan Monnier, 2020/12/14
- [elpa] externals/heap 10a68e6 29/31: Bump version numbers since we've added iterator generators., Stefan Monnier, 2020/12/14
- [elpa] externals/heap 04de075 30/31: Tidy up unnecessary macros by making them into defsubst or defun., Stefan Monnier, 2020/12/14
- [elpa] externals/heap 151a314 17/31: Added heap-merge function for merging heaps.,
Stefan Monnier <=
- [elpa] externals/heap c71bf79 27/31: Implement trie-fuzzy-match and trie-fuzzy-complete functions., Stefan Monnier, 2020/12/14