1
\$\begingroup\$

My research question was to find out whether minimizing the number of assignments in a heap lead to any time savings. The "optimized" version stores the element to sift, sift the minimum to its place and continues from the sifted element until finding the correct position, inserting the stored element. When \$n\$ array components are dislocated, only \$n + 1\$ assignments are done. (In conventional sift algorithm \$3n\$ assignments in total are performed.) Here is my code:

import java.util.Arrays;
import java.util.Random;

public class Main {

    /**
     * Conventional sift down procedure. If the array component 
     * {@code array[index]} is moved {@code n} times, {@code 3n} swaps is done.
     * 
     * @param array the target array.
     * @param index the index of the element to sift.
     */
    public static void siftDown1(int[] array, int index) {
        int leftChildIndex = (index << 1) + 1;
        int rightChildIndex = leftChildIndex + 1;
        int minIndex = index;

        while (true) {
            if (leftChildIndex < array.length 
                    && array[leftChildIndex] < array[index]) {
                minIndex = leftChildIndex;
            }

            if (rightChildIndex < array.length
                    && array[rightChildIndex] < array[minIndex]) {
                minIndex = rightChildIndex;
            }

            if (minIndex == index) {
                return;
            }

            int tmp = array[minIndex];
            array[minIndex] = array[index];
            array[index] = tmp;

            index = minIndex;
            leftChildIndex = (index << 1) + 1;
            rightChildIndex = leftChildIndex + 1;
        }
    }

    /**
     * Optimized sift down procedure. If the array component 
     * {@code array[index]} is moved {@code n} times, {@code n + 1} swaps is 
     * done.
     * 
     * @param array the target array.
     * @param index the index of the element to sift.
     */
    public static void siftDown2(int[] array, int index) {
        int leftChildIndex = (index << 1) + 1;
        int rightChildIndex = leftChildIndex + 1;
        int minIndex = index;
        int target = array[index];

        while (true) {
            if (leftChildIndex < array.length
                    && array[leftChildIndex] < target) {
                minIndex = leftChildIndex;
            }

            if (minIndex == index) {
                if (rightChildIndex < array.length
                        && array[rightChildIndex] < target) {
                    minIndex = rightChildIndex;
                }
            } else {
                if (rightChildIndex < array.length
                        && array[rightChildIndex] < array[leftChildIndex]) {
                    minIndex = rightChildIndex;
                }
            }

            if (minIndex == index) {
                array[minIndex] = target;
                return;
            }

            array[index] = array[minIndex];
            index = minIndex;
            leftChildIndex = (index << 1) + 1;
            rightChildIndex = leftChildIndex + 1;
        }
    }

    public static void buildHeap1(int[] array) {
        for (int i = array.length / 2; i >= 0; --i) {
            siftDown1(array, i);
        }
    }

    public static void buildHeap2(int[] array) {
        for (int i = array.length / 2; i >= 0; --i) {
            siftDown2(array, i);
        }
    }

    private static final Random RANDOM = new Random();

    public static void main(String[] args) {
        warmup();
        benchmark();
    }    

    private static void warmup() {
        System.out.println("Warming up...");
        int[] array1 = new int[50_000_000];

        for (int i = 0; i < array1.length; ++i) {
            array1[i] = RANDOM.nextInt(2_000_000);
        }

        int[] array2 = array1.clone();

        buildHeap1(array1);
        buildHeap2(array2);
        System.out.println("Warming up done!");
    }

    private static void benchmark() {
        int[] array1 = new int[100_000_000];

        for (int i = 0; i < array1.length; ++i) {
            array1[i] = RANDOM.nextInt(200_000_000);
        }

        int[] array2 = array1.clone();

        long start = System.currentTimeMillis();
        buildHeap1(array1);
        long end = System.currentTimeMillis();

        System.out.println("buildHeap1 in " + (end - start) + " milliseconds.");

        start = System.currentTimeMillis();
        buildHeap2(array2);
        end = System.currentTimeMillis();

        System.out.println("buildHeap2 in " + (end - start) + " milliseconds.");
        System.out.println("Algorithms agreed: " + 
                           Arrays.equals(array1, array2));
    }
}

And these are performance figures:

buildHeap1 in 1826 milliseconds.
buildHeap2 in 1665 milliseconds.
Algorithms agreed: true
\$\endgroup\$
  • \$\begingroup\$ (You know my 1st quip by hard.)(While I can see swaps in siftDown1() squinting hard enough, I feel hard pressed with siftDown2(). I'd count (/report) array writes (ignore assignments to the likes of tmp).) Good thing you state explicitly what you wanted coding this thus. \$\endgroup\$ – greybeard Dec 17 '17 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.