Kontera

Thursday, October 25, 2012

Deap -Implementation in Java


Deap

A deap is a double-ended heap that supports the double-ended priority operations of insert, delet-min, and delete-max. Similar to min-max heap but deap is faster on these operations by a constant factor, and the algorithms are simpler.

Definition: A deap is a complete binary tree that is either empty or satisfies the following properties:

   (1) The root contains no element
   (2) The left subtree is a min heap.
   (3) The right subtree is a max heap.
   (4) If the right subtree is not empty, then let i be     any node in the left subtree. Let j be the corresponding node in the right subtree. If such a j does not exist, then let j be the node  in the right subtree that corresponds to the  parent of i. The key in node i is less than or equal to that of j.

Example




Insertion into Deap



After the insertion of 4



After the insertion of 30


 

Deletion of  min Element



Implementation

/*
Program Name: Deap.java
 * Author: Sarju
 * Date: 1-10-12
 * Reference: Shiuh-Sheng Yu, Department of Information Management, National Chi Nan University
 * 
 */
 import java.io.*;
public class Deap {
    int[] deap;
    int n = 1;
    public Deap(int maxSize) {
        deap = new int[maxSize];
    }
    private boolean inMaxHeap(int i) {
        while (i > 3) {
            i /= 2;
           
         }
        if (i == 2) return false;
        return true;
    }
    private int maxPartner(int pos) {
        int offset = 1;
        int i = pos;
        while (i > 3) {
            i /= 2;
            offset *= 2;
        }
        if ((pos + offset) > n) return (pos+offset)/2;
        return pos + offset;
    }
    private int minPartner(int pos) {
        int offset = 1;
        int i = pos;
        while (i > 3) {
            i /= 2;
            offset *= 2;
        }
        return pos - offset;
    }
    private void minInsert(int at, int key) {
        for (int parent; (parent = at / 2) != 1 && key < deap[parent]; deap[at] = deap[parent], at = parent) ;
        deap[at] = key;
    }
    private void maxInsert(int at, int key) {
        for (int parent; (parent = at / 2) != 1 && key > deap[parent]; deap[at] = deap[parent], at = parent) ;
        deap[at] = key;
    }
    public int deleteMax() {
        int i, j;
        int key;
        if (n >= 3) { // if more than 2 elements
            key = deap[3];
        } else {
            n--;
            return deap[2];
        }
        int x = deap[n--];
        // while i has child, move larger to i
        for (i = 3; 2*i <= n; deap[i] = deap[j], i = j) {
            j = i * 2;
            if (j+1 <= n) {
                if (deap[j] < deap[j+1]) {
                    j++;
                }
            }
        }
        // try to put x at leaf i
        // find biggest at min partner
        j = minPartner(i);
        int biggest = j;
        if (2*j <= n) {
            biggest = 2*j;
            if (((2*j + 1) <= n) && (deap[2*j] < deap[2*j+1])) {
                biggest++;
            }
        }
        if (x < deap[biggest]) {
            // x can't put at i, must change with deap[biggest]
            deap[i] = deap[biggest];
            minInsert(biggest, x);
        } else {
            maxInsert(i, x);
        }
        return key;
    }
    public int deleteMin() {
        int i, j, key = deap[2], x = deap[n--];
        // while i has child, move smaller to i
        for (i = 2; 2*i <= n; deap[i] = deap[j], i = j) {
            j = i * 2;
            if (j+1 <= n && deap[j] > deap[j+1]) {
                j++;
            }
        }
        // try to put x at leaf i
        j = maxPartner(i);
        if (x > deap[j]) {
            deap[i] = deap[j];
            maxInsert(j, x);
        } else {
            minInsert(i, x);
        }
        return key;
    }
    public void insert(int x) {
        n++;
        if (n == deap.length) {
            System.out.println("The heap is full");
            System.exit(1);
        }
        if (n == 2) {
            deap[2] = x;
            return;
        }
        if (inMaxHeap(n)) {
            int i = minPartner(n);
            if (x < deap[i]) {
                deap[n] = deap[i];
                minInsert(i, x);
            } else {
                maxInsert(n, x);
            }
        } else {
            int i = maxPartner(n);
            if (x > deap[i]) {
                deap[n] = deap[i];
                maxInsert(i, x);
            } else {
                minInsert(n, x);
            }
        }
    }
    public void print() {
        int levelNum = 2;
        int thisLevel = 0;
        int gap = 8;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < gap-1; j++) {
                System.out.print(" ");
            }
            if (thisLevel != 0) {
                for (int j = 0; j < gap-1; j++) {
                    System.out.print(" ");
                }
            }
            if (Integer.toString(deap[i]).length() == 1) {
                System.out.print(" ");
            }
            System.out.print(deap[i]);
            thisLevel++;
            if (thisLevel == levelNum) {
                System.out.println();
                thisLevel = 0;
                levelNum *= 2;
                gap/=2;
            }
        }
        System.out.println();
        if (thisLevel != 0) {
            System.out.println();
        }
    }
    public static void main(String[] argv) {
        Deap a = new Deap(1024);
        int choice,element;
        
        try{
        do{   
        System.out.print("\n1:Insert\n2.DeleteMin\n3.DeleteMax\n4.Exit");
        System.out.print("\nEnter Your Choice:");
        DataInputStream din  = new DataInputStream(System.in);
        choice = Integer.parseInt(din.readLine());
        switch(choice){
            case 1: /*For Adding new Element*/
                    System.out.println("\nEnter the element to insert:");
                    din = new DataInputStream(System.in);
                    element = Integer.parseInt(din.readLine());
                    a.insert(element);
                    a.print();
                    break;
            case 2:
                    a.deleteMin();
                    a.print();
                    break;
            case 3:
                    a.deleteMax();
                    a.print();
           
        }
        }while(choice<4 br="br">        }
        catch(Exception e){
        }
       
    }
}