find_kth.lisp

(in-package :cl)
(declaim (optimize (speed 3)))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (dolist (p '(:cl-heap))
    (unless (find-package p)
      (ql:quickload p))))
(defpackage :find-kth-largest
  (:use :cl :cl-heap)
  (:nicknames :fkl))
(in-package :find-kth-largest)
(defun make-random-array (n)
  (let ((a (make-array n :element-type 'fixnum)))
    (dotimes (i n)
      (setf (aref a i) (random (expt 2 32))))
    a))
(defun heap (a k)
  (let ((h (make-instance 'binary-heap)))
    (dotimes (i k)
      (add-to-heap h -1))
    (dotimes (i (length a))
      (when (> (aref a i) (peep-at-heap h))
	  (pop-heap h)
	  (add-to-heap h (aref a i))))
    h))
(defun heap->list (h)
  (let ((new-heap (merge-heaps (make-instance 'binary-heap) h)))
    (loop
	  repeat (heap-size new-heap)
	  collect (pop-heap new-heap))))