From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id CAA29441; Mon, 28 Apr 2003 02:20:13 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id CAA29252 for <caml-list@pauillac.inria.fr>; Mon, 28 Apr 2003 02:20:12 +0200 (MET DST)
Received: from eposta.kablonet.com.tr ([62.248.102.66])
	by nez-perce.inria.fr (8.11.1/8.11.1) with SMTP id h3S0K9T25032
	for <caml-list@inria.fr>; Mon, 28 Apr 2003 02:20:10 +0200 (MET DST)
Received: (qmail 49857 invoked by uid 0); 28 Apr 2003 00:27:33 -0000
Received: from unknown (HELO 195.174.169.185) (exa@195.174.169.185)
  by 0 with SMTP; 28 Apr 2003 00:27:33 -0000
From: Eray Ozkural <exa@kablonet.com.tr>
Reply-To: erayo@cs.bilkent.edu.tr
Organization: Bilkent University CS Dept.
To: OCaml List <caml-list@inria.fr>
Subject: [Caml-list] heapsort and priority queue code
Date: Mon, 28 Apr 2003 03:19:43 +0300
User-Agent: KMail/1.5.9
MIME-Version: 1.0
Content-Disposition: inline
Content-Type: Multipart/Mixed;
  boundary="Boundary-00=_fOHr+gjppoKhCJV"
Message-Id: <200304280319.43986.exa@kablonet.com.tr>
X-Spam: no; 0.00; eray:01 ozkural:01 heapsort:01 listened:99 gpl:01 erayo:01 bilkent:01 ankara:01 kde:01 malfunction:01 ariza:01 printf:01 arrays:01 mutable:01 sci:01 
X-Attachments: name="heap.ml" name="heap.ml" 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk


--Boundary-00=_fOHr+gjppoKhCJV
Content-Type: text/plain;
  charset="us-ascii"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Hi there,

Here is a version of heap sort and PQ ops, maybe you have a use for it who 
knows :) Any suggested improvements over style will be carefully listened to.

license is GPL :P

Regards,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

--Boundary-00=_fOHr+gjppoKhCJV
Content-Type: text/plain;
  charset="us-ascii";
  name="heap.ml"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment; filename="heap.ml"

open Array
open Printf

type heap = { a: int array; mutable size: int }

let swap a i j = let t = a.(i) in a.(i) <- a.(j); a.(j) <- t
let print_intarray a = Array.iter (fun x->printf "%d " x) a

(* arrays start from 0 *)
(* a heap array, i index *)

let parent i = (i-1) / 2
let left i = 2*i + 1
let right i = 2*i + 2

let rec heapify h i =
  let l = ref (left i)
  and r = ref (right i)
  and largest = ref 0
  and a = h.a in
    printf "i=%d, l=%d, r=%d, hs=%d\n" i !l !r h.size;
    if !l < h.size && a.(!l) > a.(i)
    then largest := !l
    else largest := i;
    if !r < h.size && a.(!r) > a.(!largest)
    then largest := !r else ();
    if !largest <> i then
      begin
	swap a i !largest;
	heapify h !largest
      end
    else ()

let build_heap a =
  let h = { a = a; size = length a} in
    for i = (length a)/2-1 downto 0 do heapify h i done;
    h

let sort a =
  let h = build_heap a in
    for i = length a-1 downto 1 do
      swap a 0 i;
      h.size <- h.size-1;
      heapify h 0
    done

exception Underflow

let extract_max h =
  if h.size < 1 then raise Underflow else
    let a = h.a in
    let max = a.(0) in
      a.(0) <- a.(h.size-1);
      h.size <- h.size - 1;
      heapify h 0;
      max
      
let insert h key =
  h.size <- h.size + 1;
  let i = ref (h.size - 1) in (* last node *)
  let a = h.a in
    while !i > 0 && a.(parent !i) < key do
      a.(!i) <- a.(parent !i);
      i := parent !i
    done;
    a.(!i) <- key

let test () =
  begin
    let a = [| 5; 13; 2; 25; 7; 16; 20; 8; 4 |] in
      sort a;
      print_intarray a; printf "\n"
  end;
  begin
    let h = {a = [| 15;13;9;5;12;8;7;4;0;6;2;1;0;0;0 |]; size=12} in
      insert h 3
  end;
  begin
    let h = {a = [| 15;13;9;5;12;8;7;4;0;6;2;1 |]; size=12} in
    let t = extract_max h in
      printf "top is %d\n" t
  end


--Boundary-00=_fOHr+gjppoKhCJV--

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners