Material‎ > ‎

IntSet

Das Archiv beinhaltet auch eine Makefile, um die Programme zu bauen und auszuführen. 


IIntSet.java

/**
 * An interface for sets of integers.
 * All methods must throw an IllegalArgumentException for negative arguments.
 * This is similar to Java's Set<Integer>, but potentially significantly more efficient.
 */
interface IIntSet {
    /**
     * Add x to the set.
     */
    void add(int x);

    /**
     * Check whether x is a member of the set.
     */
    boolean contains(int x);

    /**
     * Delete x from the set.
     */
    void remove(int x);
}

IntSetTest.java

import junit.framework.TestCase;
import java.util.Random;
import java.util.HashSet;

// Unit tests for IntSet

public class IntSetTest extends TestCase {
    // Override this in subclasses to create test suites for
    // other implementations.

    IIntSet create() {
        return new MockIntSet();
    }

    // Check that all methods throw exceptions for negative keys.

    public void testAddException() {
        IIntSet set = create();
        for(int i=0;i<100;i++) set.add(i);
        Exception exception = null;
        try {
            set.add(-1);
        } catch(IllegalArgumentException e) {
            exception = e;
        }
        assertNotNull("exception expected",exception);
    }

    public void testDeleteException() {
        IIntSet set = create();
        for(int i=0;i<100;i++) set.add(i);
        Exception exception = null;
        try {
            set.remove(-1);
        } catch(IllegalArgumentException e) {
            exception = e;
        }
        assertNotNull("exception expected",exception);
    }

    public void testContainsException() {
        IIntSet set = create();
        for(int i=0;i<100;i++) set.add(i);
        Exception exception = null;
        try {
            set.remove(-1);
        } catch(IllegalArgumentException e) {
            exception = e;
        }
        assertNotNull("exception expected",exception);
    }

    // Test simple set membership.

    public void testMembership() {
        IIntSet set = create();
        for(int i=0;i<10;i+=2)
            set.add(i);
        for(int i=0;i<10;i+=2)
            assertTrue("contains",set.contains(i));
        for(int i=10;i<20;i++)
            assertFalse("contains",set.contains(i));
        assertFalse("contains",set.contains(3));
        assertTrue("contains",set.contains(4));
        set.remove(4);
        assertFalse("contains",set.contains(4));
    }

    // More extensive tests using pseudo-randomly generated data.
    // To ensure repeatability, we use a fixed seed.

    public void testRandom() {
        Random random = new Random(93);
        IIntSet set = create();
        HashSet<Integer> lset = new HashSet<Integer>();
        for(int i=0;i<10000;i++) {
            int j = random.nextInt(1000);
            int c = random.nextInt(3);
            // System.out.println(">>> "+c+" : "+j+" ["+i+"]");
            switch(c) {
            case 0:
                assertEquals("random set",set.contains(j),lset.contains(j));
                set.add(j);
                lset.add(j);
                assertEquals("random set",set.contains(j),lset.contains(j));
                break;
            case 1:
                assertEquals("random set",set.contains(j),lset.contains(j));
                set.remove(j);
                lset.remove(j);
                assertEquals("random set",set.contains(j),lset.contains(j));
                break;
            case 2:
                assertEquals("random set",set.contains(j),lset.contains(j));
                break;
            }
        }
    }
}


MockIntSet.java

// A simple implementation of IIntSet using linear search.
// This can't resize the array and will fail with sets larger
//  than MAXSIZE.

public class MockIntSet implements IIntSet {
    // data[0...fill-1] contains the elements

    private int fill;
    private int[] data;

    // MAXSIZE for this implementation

    private final static int MAXSIZE = 10000;

    public MockIntSet() {
        fill = 0;
        data = new int[MAXSIZE];
    }

    // find using linear search

    int find(int x) {
        if(x<0) throw new IllegalArgumentException();
        for(int i=0;i<fill;i++)
            if(data[i]==x) return i;
        return -1;
    }

    // contains() is a simple wrapper around find()

    public boolean contains(int x) {
        return find(x)>=0;
    }

    // remove the given key x; this assumes that the
    // elements in the array are unique (since it removes
    // only one occurrence)

    public void remove(int x) {
        int index = find(x);
        if(index<0) return;

        // NB: this works even if the element to be removed
        // is already the last element
        data[index] = data[--fill];
        data[fill] = 0;
    }

    // add an element

    public void add(int x) {
        // don't add if it already exists; this ensures that
        // each key exists only once
        if(contains(x)) return;

        // add it to the end
        // NB: in this mock implementation, we may get an
        // array bounds violation
        data[fill++] = x;
    }
}

IntSetTest.java

import junit.framework.TestCase;
import java.util.Random;
import java.util.HashSet;

// Unit tests for IntSet

public class IntSetTest extends TestCase {
    // Override this in subclasses to create test suites for
    // other implementations.

    IIntSet create() {
        return new MockIntSet();
    }

    // Check that all methods throw exceptions for negative keys.

    public void testAddException() {
        IIntSet set = create();
        for(int i=0;i<100;i++) set.add(i);
        Exception exception = null;
        try {
            set.add(-1);
        } catch(IllegalArgumentException e) {
            exception = e;
        }
        assertNotNull("exception expected",exception);
    }

    public void testDeleteException() {
        IIntSet set = create();
        for(int i=0;i<100;i++) set.add(i);
        Exception exception = null;
        try {
            set.remove(-1);
        } catch(IllegalArgumentException e) {
            exception = e;
        }
        assertNotNull("exception expected",exception);
    }

    public void testContainsException() {
        IIntSet set = create();
        for(int i=0;i<100;i++) set.add(i);
        Exception exception = null;
        try {
            set.remove(-1);
        } catch(IllegalArgumentException e) {
            exception = e;
        }
        assertNotNull("exception expected",exception);
    }

    // Test simple set membership.

    public void testMembership() {
        IIntSet set = create();
        for(int i=0;i<10;i+=2)
            set.add(i);
        for(int i=0;i<10;i+=2)
            assertTrue("contains",set.contains(i));
        for(int i=10;i<20;i++)
            assertFalse("contains",set.contains(i));
        assertFalse("contains",set.contains(3));
        assertTrue("contains",set.contains(4));
        set.remove(4);
        assertFalse("contains",set.contains(4));
    }

    // More extensive tests using pseudo-randomly generated data.
    // To ensure repeatability, we use a fixed seed.

    public void testRandom() {
        Random random = new Random(93);
        IIntSet set = create();
        HashSet<Integer> lset = new HashSet<Integer>();
        for(int i=0;i<10000;i++) {
            int j = random.nextInt(1000);
            int c = random.nextInt(3);
            // System.out.println(">>> "+c+" : "+j+" ["+i+"]");
            switch(c) {
            case 0:
                assertEquals("random set",set.contains(j),lset.contains(j));
                set.add(j);
                lset.add(j);
                assertEquals("random set",set.contains(j),lset.contains(j));
                break;
            case 1:
                assertEquals("random set",set.contains(j),lset.contains(j));
                set.remove(j);
                lset.remove(j);
                assertEquals("random set",set.contains(j),lset.contains(j));
                break;
            case 2:
                assertEquals("random set",set.contains(j),lset.contains(j));
                break;
            }
        }
    }
}

LinearIntSet.java

// Simple class implementing IIntSet with linear search.
// Uses doubling of the array in order to grow dynamically.

public class LinearIntSet implements IIntSet {
    // data[0...fill-1] contains the elements

    private int[] data;
    private int fill;

    // Create an empty set.

    public LinearIntSet() {
        fill = 0;
        data = new int[3];
    }

    // Find by linear search.

    int find(int x) {
        if(x<0) throw new IllegalArgumentException();
        for(int i=0;i<fill;i++)
            if(data[i]==x) return i;
        return -1;
    }

    // Check for membership using internal find() method.

    public boolean contains(int x) {
        return find(x)>=0;
    }

    // Remove by removing the last element and moving it into the
    // position of the found element (if any).

    public void remove(int x) {
        int index = find(x);
        if(index<0) return;

        // NB: this works even if the found element is the last
        // element.
        data[index] = data[--fill];
        data[fill] = 0;
    }

    // Add an element to the set.

    public void add(int x) {
        // This check ensures that elements are unique.  The remove() operation
        // relies on this.
        if(contains(x)) return;

        // Grow the array if it has become too full.
        if(fill==data.length) {
            int[] ndata = new int[data.length*2+1];
            for(int i=0;i<fill;i++) ndata[i] = data[i];
            data = ndata;
        }

        // Add the new element at the end.
        data[fill++] = x;
    }
}

LinearIntSetTest.java

import junit.framework.TestCase;
import java.util.Random;

public class LinearIntSetTest extends IntSetTest {
    IIntSet create() {
        return new LinearIntSet();
    }
}

BsInetSet.java

// An IIntSet implementation using binary search.  Data is stored
// similar to the LinearIntSet, but find() is implemented using binary
// search.  Binary search requires a sorted array.  Therefore, the
// implementation keeps track of whether elements have been
// added/removed and/or the array has been sorted via the boolean
// sorted flag.  When elements have been added/removed, the array is
// assumed to be unsorted and is sorted when find() is called.

public class BsIntSet implements IIntSet {
    static boolean verbose = true;

    // Set elements are stored in data[0...fill]
    int fill;
    int[] data;
    boolean sorted;

    public BsIntSet() {
        fill = 0;
        data = new int[3];
        sorted = true;
    }

    // An overridable wrapper for the sort function.
    // By default, we use quicksort.

    void sort() {
        IntQuicksort.quicksort(data,0,fill);
    }

    // This find implementation uses binary search.  If it doesn't
    // know whether the array is sorted, it sorts it first.

    int find(int x) {
        if(x<0) throw new IllegalArgumentException();

        // If we can't be sure that the array is sorted, sort it.
        if(!sorted) {
            sort();
            sorted = true;
        }

        // The actual binary search algorithm.
        int lo = 0;
        int hi = fill-1;
        while(lo<=hi) {
            int center = (lo+hi)/2;
            if(x==data[center]) return center;
            else if(x<data[center]) hi = center-1;
            else lo = center+1;
        }
        return -1;
    }

    // The contains() method is implemented using binary search.

    public boolean contains(int x) {
        return find(x)>=0;
    }

    // For adding and removing elements, we also need to check whether
    // elements are already part of the set.  Since sorting the set
    // again and again is at best linear time, we might as well use a
    // linear search for these checks.

    int linear_find(int x) {
        // check for non-negative arguments
        if(x<0) throw new IllegalArgumentException();

        // if it's sorted, use the fast implementation
        if(sorted) return find(x);

        // otherwise, use linear search
        for(int i=0;i<fill;i++)
            if(data[i]==x) return i;

        return -1;
    }

    // Add an element.

    public void add(int x) {
        // If it already exists, don't add it again.
        if(linear_find(x)>=0) return;

        // Grow the array if necessary.
        if(fill==data.length) {
            int[] ndata = new int[data.length*2+1];
            for(int i=0;i<fill;i++) ndata[i] = data[i];
            data = ndata;
        }

        // Finally, add the element.
        data[fill++] = x;

        // After adding it, update the sorted flag.  If elements are
        // inserted in sorted order, the flag will actually remain
        // true.
        if(fill>1 && data[fill-1]<data[fill-2]) sorted = false;
    }

    public void remove(int x) {
        // Check if it exists; do nothing if it doesn't.
        int index = linear_find(x);
        if(index<0) return;

        // Remove the element.
        data[index] = data[--fill];

        // Set the old location to an illegal value.
        data[fill] = -1;

        // After removal, the sorted property is not guaranteed anymore.
        sorted = false;
    }
}

BsIntSetTest.java

import junit.framework.TestCase;
import java.util.Random;

// Unit tests for BsIntSet; these are the same as the basic
// IntSet tests.

public class BsIntSetTest extends IntSetTest {
    IIntSet create() {
        return new BsIntSet();
    }
}

NdHashIntSet.java

// An IntSet implemented using hash tables, but without remove() operation.

public class NdHashIntSet implements IIntSet {
    // The hash table itself.

    private int[] data;

    // The total number of buckets in use.  We keep track of
    // this to make sure we know when to rehash the data.

    private int total;

    // Empty buckets are marked with this value.
    // Note that negative integers are not permitted in
    // any IntSet.

    final static int EMPTY = -1;

    // Initialize the IntSet with a given size (>0).  This only affects efficiency,
    // not correctness; the table will get resized as necessary later.

    public NdHashIntSet(int n) {
        if(n<1) throw new IllegalArgumentException();
        init(n);
    }

    // Default constructor initializes a small hash table (grows as needed).

    public NdHashIntSet() {
        init(10);
    }

    // Actually perform the initialization of the hash table.  All
    // slots are initialized to EMPTY.

    void init(int n) {
        total = 0;
        data = new int[n];
        for(int i=0;i<data.length;i++) data[i] = EMPTY;
    }

    // Compute a "hash function" for the given integer x and the
    // number of buckets n.

    int hash(int x,int n) {
        assert x>=0 && x<n;
        double y = x * 3.29308420842089 + 0.1098290808092;
        double z = y - (int)y;
        return (int)(z*n);
    }

    // Find the bucket relevant to the key x.
    // If add==false, always returns the bucket containing x, or -1.
    // If add==true, always returns an empty bucket, or -1
    // That bucket is either the bucket containing x or an empty bucket.
    // This also checks that x is >=0.

    int bucket(int x,boolean add) {
        if(x<0) throw new IllegalArgumentException();
        int n = data.length;
        int bucket = hash(x,n);
        for(int i=0;i<n;i++) {
            int value = data[(bucket+i)%n];
            if(add) {
                if(value==EMPTY) return (bucket+i)%n;
                if(value==x) return -1;
            } else {
                if(value==EMPTY) return -1;
                if(value==x) return (bucket+i)%n;
            }
        }
        // If we wrap around completely, the table has gotten too full;
        // this should never happen.
        throw new IllegalStateException();
    }

    // Check whether the key x is contained in the table.

    public boolean contains(int x) {
        int b = bucket(x,false);
        return b>=0;
    }

    // Add all the elements of the current hash table to a new, bigger hash table,
    // then replace this table with the new table.

    void refresh() {
        NdHashIntSet nset = new NdHashIntSet(data.length*2+1);
        for(int i=0;i<data.length;i++)
            if(data[i]>=0)
                nset.add(data[i]);
        data = nset.data;
        total = nset.total;
    }

    // Add the key x to this hash table.

    public void add(int x) {
        // If the table has gotten too full, make this table larger.
        if(total>=data.length/2) refresh();

        // Find a bucket for adding the key.
        int b = bucket(x,true);

        // No bucket found (=key already exists).
        if(b<0) return;

        // Otherwise, add the element and keep track of the fact that the
        // table is now fuller.
        data[b] = x;
        total++;
    }

    // Removing isn't implemented; we just raise an exception.

    public void remove(int x) {
        throw new IllegalStateException();
    }
}

NdHashIntSetTest.java

import junit.framework.TestCase;
import java.util.Random;
import java.util.HashSet;

// Unit tests for IntSet.  This tests everything without the remove() operation.

public class NdHashIntSetTest extends TestCase {
    // Override this in subclasses to test other implementations.

    IIntSet create() {
        return new MockIntSet();
    }

    // Check that exceptions are thrown.

    public void testAddException() {
        IIntSet set = create();
        for(int i=0;i<100;i++) set.add(i);
        Exception exception = null;
        try {
            set.add(-1);
        } catch(IllegalArgumentException e) {
            exception = e;
        }
        assertNotNull("exception expected",exception);
    }

    public void testDeleteException() {
        IIntSet set = create();
        for(int i=0;i<100;i++) set.add(i);
        Exception exception = null;
        try {
            set.remove(-1);
        } catch(IllegalArgumentException e) {
            exception = e;
        }
        assertNotNull("exception expected",exception);
    }

    // Simple membership test.

    public void testMembership() {
        IIntSet set = create();
        for(int i=0;i<10;i+=2)
            set.add(i);
        for(int i=0;i<10;i+=2)
            assertTrue("contains",set.contains(i));
        for(int i=10;i<20;i++)
            assertFalse("contains",set.contains(i));
        assertFalse("contains",set.contains(3));
        assertTrue("contains",set.contains(4));
    }

    // Tests on random data.

    public void testRandom() {
        Random random = new Random(117);
        IIntSet set = create();
        HashSet<Integer> lset = new HashSet<Integer>();
        for(int i=0;i<10000;i++) {
            int j = random.nextInt(1000);
            int c = random.nextInt(2);
            switch(c) {
            case 0:
                set.add(j);
                lset.add(j);
                break;
            case 1:
                assertEquals("random set",set.contains(j),lset.contains(j));
                break;
            }
        }
    }
}

HashIntSet.java

// An IntSet implemented using hash tables, including remove()

public class HashIntSet implements IIntSet {
    // The hash table itself.

    private int[] data;

    // The total number of buckets in use.  We keep track of
    // this to make sure we know when to rehash the data. This
    // counts deleted buckets.

    private int total;

    // The number of active buckets, i.e. buckets actually
    // containing data.

    private int active;

    // Buckets can now be in three states: EMPTY, containing data, or DELETED
    final static int EMPTY = -1;
    final static int DELETED = -2;

    // Initialize the IntSet with a given size (>0).  This only affects efficiency,
    // not correctness; the table will get resized as necessary later.

    public HashIntSet(int n) {
        init(n);
    }

    // Default constructor initializes a small hash table (grows as needed).

    public HashIntSet() {
        init(10);
    }

    // Actually perform the initialization of the hash table.  All
    // slots are initialized to EMPTY.

    void init(int n) {
        total = 0;
        data = new int[n];
        for(int i=0;i<data.length;i++) data[i] = EMPTY;
    }

    // Compute a "hash function" for the given integer x and the
    // number of buckets n.

    int hash(int x,int n) {
        assert x>=0 && x<n;
        double y = x * 3.29308420842089 + 0.1098290808092;
        double z = y - (int)y;
        return (int)(z*n);
    }

    // Find the bucket relevant to the key x.
    // If add==false, always returns the bucket containing x, or -1.
    // If add==true, always returns an empty bucket, or -1
    // That bucket is either the bucket containing x or an empty bucket.
    // This also checks that x is >=0.

    int bucket(int x,boolean add) {
        if(x<0) throw new IllegalArgumentException();
        int n = data.length;
        int bucket = hash(x,n);
        for(int i=0;i<n;i++) {
            int b = (bucket+i)%n;
            int value = data[b];
            if(add) {
                if(value==EMPTY) return b;
                if(value==x) return -1;
            } else {
                if(value==EMPTY) return -1;
                if(value==x) return b;
            }
        }
        // If we wrap around completely, the table has gotten too full;
        // this should never happen.
        throw new IllegalStateException();
    }

    // Check whether the key x is contained in the table.

    public boolean contains(int x) {
        int b = bucket(x,false);
        return b>=0;
    }

    // Add all the elements of the current hash table to a new, bigger hash table,
    // then replace this table with the new table.

    void refresh() {
        HashIntSet nset = new HashIntSet(active*2+1);
        for(int i=0;i<data.length;i++)
            if(data[i]>=0)
                nset.add(data[i]);
        data = nset.data;
        total = nset.total;
        active = nset.active;
    }

    // Add the key x to this hash table.

    public void add(int x) {
        // If the table has gotten too full, make this table larger.
        if(total>=data.length/2) refresh();

        // Find a bucket for adding the key.
        int b = bucket(x,true);

        // No bucket found (=key already exists).
        if(b<0) return;

        // Check whether we are refilling a DELETED slot; if not,
        // one more total slot is used afterwards.
        int value = data[b];
        if(value!=DELETED) total++;

        // Otherwise, add the element and keep track of the fact that the
        // table now contains another active entry.
        data[b] = x;
        active++;
    }

    // We remove an element by finding the slot containing the key.
    // We can't just set it to empty because this may be part of a run of non-empty slots
    // that are involved in some other collision.  Therefore, we set it to a special value
    // DELETED.

    public void remove(int x) {
        // We find a bucket as we do for membership.
        int b = bucket(x,false);

        // No bucket found = nothing to do.
        if(b<0) return;

        // If we find a bucket, we set it to the special DELETED value.
        data[b] = DELETED;
        active--;

        // Refresh the table if too many deleted elements are in it.
        if(active<total/2) refresh();
    }
}

HastIntSetTest.java

import junit.framework.TestCase;
import java.util.Random;

public class HashIntSetTest extends IntSetTest {
    IIntSet create() {
        return new HashIntSet();
    }
}

HastIntSet2Test.java

import junit.framework.TestCase;
import java.util.Random;

// This tests HashIntSet without remove (it is useful for debugging, to
// see whether a bug comes from remove() or not.

public class HashIntSet2Test extends NdHashIntSetTest {
    IIntSet create() {
        return new HashIntSet();
    }
}

IntBubblesort.java

import java.util.Random;

// A very simple sort implementation for integer arrays, used mainly for testing.

public class IntBubblesort {
    static void swap(int[] f,int i,int j) {
        int temp = f[i];
        f[i] = f[j];
        f[j] = temp;
    }

    static void bubblesort(int[] a) {
        for(int i=0;i<a.length;i++) {
            for(int j=0;j<a.length-1;j++) {
                if(a[j]>a[j+1]) swap(a,j,j+1);
            }
        }
    }
}


SortTest.java

import junit.framework.TestCase;
import java.util.Random;

// Unit tests for sorting.

public class SortTest extends TestCase {
    void sort(int[] a) {
        IntBubblesort.bubblesort(a);
    }

    boolean contains(int[] a,int x) {
        for(int i=0;i<a.length;i++)
            if(a[i]==x) return true;
        return false;
    }

    // Make sure the base cases work correctly.

    public void testBasecases() {
        int[] a0 = new int[]{};
        sort(a0);
        int[] a1 = new int[]{9997};
        sort(a1);
        assertEquals("sort base case",a1[0],9997);
    }

    // Now test on a lot of random data.

    public void testRandom() {
        Random random = new Random(195);
        for(int round=0;round<100;round++) {
            int n = 3+random.nextInt(1000);
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = random.nextInt();
            int[] b = new int[n];
            for(int i=0;i<n;i++) b[i] = a[i];
            sort(b);
            for(int i=0;i<b.length-1;i++)
                assertTrue("order",b[i]<=b[i+1]);
            for(int i=0;i<a.length;i++)
                assertTrue("membership",contains(b,a[i]));
            for(int i=0;i<b.length;i++)
                assertTrue("membership",contains(a,b[i]));
        }
    }
}

IntQuicksort.java

import java.util.Random;

// An efficient implementation of the Quicksort algorithm on int[] arrays.

public class IntQuicksort {

    // Short notation for swapping two elements.

    static void swap(int[] f,int i,int j) {
        int temp = f[i];
        f[i] = f[j];
        f[j] = temp;
    }

    // Split the array elements from f[start] ... f[end-1]
    // into two portions and return a split index.

    // Every element with index less than split has
    // a value less than f[split], and every element with
    // index greater than split has a value greater or equal
    // to f[split].

    static int split(int[] f,int start,int end) {
        // Use the last element of the range as a pivot.
        // We exclude that from splitting for now.

        int pivot = f[end-1];

        int i = start; // first element in range
        int j = end-2; // last element in range

        // Advance inwards until we have two elements
        // the violate the condition; swap them and continue
        // until we meet in the middle..

        for(;;) {
            while(f[i]<pivot) i++;
            while(j>=i && f[j]>=pivot) --j;
            if(i>j) break;
            swap(f,i,j);
        }

        // Now that we have met in the middle, we move the
        // pivot value into the middle position.

        swap(f,i,end-1);

        // Finally, return the position where we have split
        // the array.  This position also contains the pivot value.

        return i;
    }

    // Quicksort now becomes a simple recursive procedure:
    // this function sorts the elements f[start]...f[end-1].

    public static void quicksort(int[] f,int start,int end) {
        // If the subarray contains only 0 or 1 elements,
        // there is nothing to be done.

        if(end-start<=1) return;

        // Split the array into three parts: strictly smaller elements,
        // the pivot element, and elements greater than or equal to the
        // pivot.  The pivot is at position s.

        int s = split(f,start,end);

        // Now recursively sort the first part.

        quicksort(f,start,s);

        // And now recursively sort the third part.  Note that it is
        // important that we do not include the pivot element here,
        // otherwise we get infinite loops.

        quicksort(f,s+1,end);
    }

    // This overloaded quicksort procedure works for the entire array by default.

    public static void quicksort(int[] f) {
        quicksort(f,0,f.length);
    }

    // Try it out with a little bit of random data.

    public static void main(String[] args) {
        Random random = new Random(77);

        int[] a = new int[20];
        for(int i=0;i<a.length;i++)
            a[i] = random.nextInt(100);

        for(int i=0;i<a.length;i++) System.out.print(""+a[i]+" ");
        System.out.println();
        quicksort(a);
        for(int i=0;i<a.length;i++) System.out.print(""+a[i]+" ");
        System.out.println();
    }
}

QuickSortTest.java

import junit.framework.TestCase;
import java.util.Random;

public class QuickSortTest extends SortTest {
    void sort(int[] a) {
        IntQuicksort.quicksort(a);
    }
}

IIntHeap.java
/**
 * A heap (a kind of priority queue).
 */
interface IIntHeap {
    /**
     * Insert an element into the heap.
     */
    void insert(int x);
    /**
     * Extract the maximum element.
     */
    int extract();
};

IntHeap.java

import java.util.Random;

public class IntHeap implements IIntHeap {
    // Implicitly, the heap is an almost complete binary tree.
    // The nodes are stored in the elements data[0] ... data[end-1].

    private int[] data;
    private int end;

    // The links between nodes are implicitly encoded in the indexes.
    // The following give us the parent, left, and right
    // nodes for the given node with index i.  A non-existent node is represented
    // by the special value "nil".
    // The heap property is that if A is the parent of B, then data[A] >= data[B]

    int nil = -1;

    int parent(int i) {
        if(i==0) return nil;
        return i/2;
    }

    int left(int i) {
        if(2*i>=end) return nil;
        return 2*i;
    }

    int right(int i) {
        if(2*i+1>=end) return nil;
        return 2*i+1;
    }

    // Initialize the heap with a given maximum size.

    public IntHeap(int n) {
        data = new int[n];
        end = 0;
    }

    // Initialize the heap with a given array.
    // The data structure guarantees that if we
    // add n elements, only elements data[0]...data[n-1]
    // will be altered (we use that below).

    public IntHeap(int[] data) {
        this.data = data;
        end = 0;
    }

    // Swap two elements of the data array.

    void swap(int i,int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    // Conceptually, put the new element at the next free slot,
    // then "bubble it up" as far as it needs to go to restore
    // the heap property.

    public void insert(int x) {
        int i = end++;
        while(parent(i)!=nil && x>data[parent(i)]) {
            data[i] = data[parent(i)];
            i = i/2;
        }
        data[i] = x;
    }

    // The maximum element is found at the root (index=0).  We
    // take it out and replace it with the last element from the
    // array.  However, now the heap property isn't satisfied anymore,
    // so we recursively restore that by callin the heapify procedure.

    public int extract() {
        int result = data[0];
        data[0] = data[--end];
        heapify(0);
        return result;
    }

    // The heapify procedure checks whether the heap property is
    // satisfied, and if not restores it for this node.  If that
    // changes some child node, it calls itself recursively to restore
    // the heap property of the child node.

    // We could do this with a bunch of if statements, but it's easier
    // just to compute the index m of the maximum element among the
    // current element and its two children.

    void heapify(int i) {
        int m = i;
        if(left(i)!=nil && data[left(i)]>data[m]) m = left(i);
        if(right(i)!=nil && data[right(i)]>data[m]) m = right(i);
        if(m!=i) {
            swap(i,m);
            heapify(m); // tail recursive, could replace with loop
        }
    }

    // Conceptually, heapsort is just taking all the elements from the
    // input array, inserting them into a priority queue, and the extracting
    // the maximum from the priority queue and putting it back into the array
    // in order.

    // The neat computational trick is that the heap and the input array can
    // actually share storage if we are careful, since the heap grows from
    // the left of the array, one by one.  So, we remove elements from the array
    // one-by-one and add them to a heap that happens to share the same storate.
    // And for extraction, we reverse the process.

    public static void heapsort(int[] a) {
        // Heap h = new Heap(new int[a.length]);
        IntHeap h = new IntHeap(a);
        for(int i=0;i<a.length;i++)
            h.insert(a[i]);
        for(int i=a.length-1;i>=0;i--)
            a[i] = h.extract();
    }

    public static void main(String[] args) {
        Random random = new Random(42);
        int[] a = new int[20];
        for(int i=0;i<a.length;i++)
            a[i] = random.nextInt(100);

        for(int i=0;i<a.length;i++) System.out.print(""+a[i]+" ");
        System.out.println();
        heapsort(a);
        for(int i=0;i<a.length;i++) System.out.print(""+a[i]+" ");
        System.out.println();
    }
};

HeapSortTest.java

import junit.framework.TestCase;
import java.util.Random;

public class HeapSortTest extends SortTest {
    void sort(int[] a) {
        IntHeap.heapsort(a);
    }
}

ċ
IntSetCollection.zip
(15k)
Ludwig Schmidt-Hackenberg,
10.02.2011, 13:14
Comments