We’re rewarding the question askers & reputations are being recalculated! Read more.
2 fixed grammer
source | link
  1. The API of your class: in my opinion, there should be one more method: getMin that returns the minimum element but not removes it. The only way to get it now without deleting is to call deleteMin and then re-insert it into the heap, which is not convenientinconvenient and inefficient.

  2. There is a bug in the deleteMin method. The fact that pos * 2 + 1 is less than size does not imply that pos * 2 + 2. It can lead to a NullPointerException. I have written a simple unit test that exposes the problem:

    import org.junit.Test;
    
    import static org.junit.Assert.*;
    
    public class HeapTest {
    
        @Test
        public void testDelete() throws Exception {
            Heap<String> aHeap = new Heap<String>();
            aHeap.insert("a");
            aHeap.insert("b");
            aHeap.insert("c");
            assertEquals("a", aHeap.deleteMin());
        }
    }
    

    The result:

    java.lang.NullPointerException
        at java.lang.String.compareTo(String.java:1142)
        at java.lang.String.compareTo(String.java:111)
        at Heap.deleteMin(Heap.java:33)
        at HeapTest.testDelete(HeapTest.java:13)
    

    You should always test your code in a systematic manner. Unit tests are a good way to do it. They will help you to find and fix bugs and to make sure that it works properly(but not to prove its correctness, of course). They will increase maintainability and reliability of your code. You should write unit tests for all public methods. Do not forget to test edge cases(deleting an element from an empty heap and so on).

  3. You expand an array when necessary, but you never shrink it. It can lead to a big memory overhead. For example, if we insert a lot elements into the heap and then remove most of them, the array will not shrink, consuming much more memory than necessary. You can fix it by either adding a shrinkArray method or by using a List instead of an array here. An ArrayList can handle all required operations for you. So I would use it, unless you decided not to use a List on purpose as an exercise. If it is the case, I'd still recommend creating another class that implements the List interface(or provides a similar functionality) to decouple a heap from a dynamic array. It will make your code more readable, flexible(what if you decide to change the implementation of a dynamic array one day?) and testable.

  4. Code style:

    • It is conventional to surround binary operators with whitespaces. There should also a whitespace between an if, for or while keyword and an opening parenthesis. Here is a small piece of your code rewritten according to the style conventions:

      while (pos != 0 && array[pos].compareTo(array[pos / 2]) < 0) {
          temp = array[pos / 2];
          array[pos / 2] = array[pos];
          array[pos] = temp;
          pos /= 2;
      }
      
    • Blank lines: a lot of blank lines inside one method don't look good, in my opinion. They can be used for separating different logical blocks of code from each other(but in this case it might be better to create two separate methods instead), but they are definitely redundant in small methods(which is the case here).

    • In general, it is possible to make your code more concise by using the Java standard library. For instance, you can use an Arrays.copyOf method instead of the expandArray. But I believe that it is fine here because it is an exercise, not a production code(otherwise, you could have just used a PriorityQueue, but that's obviously not what you want in this case).

  5. You should write doc comments for all public classes and methods.

  1. The API of your class: in my opinion, there should be one more method: getMin that returns the minimum element but not removes it. The only way to get it now without deleting is to call deleteMin and then re-insert it into the heap, which is not convenient and inefficient.

  2. There is a bug in the deleteMin method. The fact that pos * 2 + 1 is less than size does not imply that pos * 2 + 2. It can lead to a NullPointerException. I have written a simple unit test that exposes the problem:

    import org.junit.Test;
    
    import static org.junit.Assert.*;
    
    public class HeapTest {
    
        @Test
        public void testDelete() throws Exception {
            Heap<String> aHeap = new Heap<String>();
            aHeap.insert("a");
            aHeap.insert("b");
            aHeap.insert("c");
            assertEquals("a", aHeap.deleteMin());
        }
    }
    

    You should always test your code in a systematic manner. Unit tests are a good way to do it. They will help you to find and fix bugs and to make sure that it works properly(but not to prove its correctness, of course). They will increase maintainability and reliability of your code. You should write unit tests for all public methods. Do not forget to test edge cases(deleting an element from an empty heap and so on).

  3. You expand an array when necessary, but you never shrink it. It can lead to a big memory overhead. For example, if we insert a lot elements into the heap and then remove most of them, the array will not shrink, consuming much more memory than necessary. You can fix it by either adding a shrinkArray method or by using a List instead of an array here. An ArrayList can handle all required operations for you. So I would use it, unless you decided not to use a List on purpose as an exercise. If it is the case, I'd still recommend creating another class that implements the List interface(or provides a similar functionality) to decouple a heap from a dynamic array. It will make your code more readable, flexible(what if you decide to change the implementation of a dynamic array one day?) and testable.

  4. Code style:

    • It is conventional to surround binary operators with whitespaces. There should also a whitespace between an if, for or while keyword and an opening parenthesis. Here is a small piece of your code rewritten according to the style conventions:

      while (pos != 0 && array[pos].compareTo(array[pos / 2]) < 0) {
          temp = array[pos / 2];
          array[pos / 2] = array[pos];
          array[pos] = temp;
          pos /= 2;
      }
      
    • Blank lines: a lot of blank lines inside one method don't look good, in my opinion. They can be used for separating different logical blocks of code from each other(but in this case it might be better to create two separate methods instead), but they are definitely redundant in small methods(which is the case here).

    • In general, it is possible to make your code more concise by using the Java standard library. For instance, you can use an Arrays.copyOf method instead of the expandArray. But I believe that it is fine here because it is an exercise, not a production code(otherwise, you could have just used a PriorityQueue, but that's obviously not what you want in this case).

  5. You should write doc comments for all public classes and methods.

  1. The API of your class: in my opinion, there should be one more method: getMin that returns the minimum element but not removes it. The only way to get it now without deleting is to call deleteMin and then re-insert it into the heap, which is inconvenient and inefficient.

  2. There is a bug in the deleteMin method. The fact that pos * 2 + 1 is less than size does not imply that pos * 2 + 2. It can lead to a NullPointerException. I have written a simple unit test that exposes the problem:

    import org.junit.Test;
    
    import static org.junit.Assert.*;
    
    public class HeapTest {
    
        @Test
        public void testDelete() throws Exception {
            Heap<String> aHeap = new Heap<String>();
            aHeap.insert("a");
            aHeap.insert("b");
            aHeap.insert("c");
            assertEquals("a", aHeap.deleteMin());
        }
    }
    

    The result:

    java.lang.NullPointerException
        at java.lang.String.compareTo(String.java:1142)
        at java.lang.String.compareTo(String.java:111)
        at Heap.deleteMin(Heap.java:33)
        at HeapTest.testDelete(HeapTest.java:13)
    

    You should always test your code in a systematic manner. Unit tests are a good way to do it. They will help you to find and fix bugs and to make sure that it works properly(but not to prove its correctness, of course). They will increase maintainability and reliability of your code. You should write unit tests for all public methods. Do not forget to test edge cases(deleting an element from an empty heap and so on).

  3. You expand an array when necessary, but you never shrink it. It can lead to a big memory overhead. For example, if we insert a lot elements into the heap and then remove most of them, the array will not shrink, consuming much more memory than necessary. You can fix it by either adding a shrinkArray method or by using a List instead of an array here. An ArrayList can handle all required operations for you. So I would use it, unless you decided not to use a List on purpose as an exercise. If it is the case, I'd still recommend creating another class that implements the List interface(or provides a similar functionality) to decouple a heap from a dynamic array. It will make your code more readable, flexible(what if you decide to change the implementation of a dynamic array one day?) and testable.

  4. Code style:

    • It is conventional to surround binary operators with whitespaces. There should also a whitespace between an if, for or while keyword and an opening parenthesis. Here is a small piece of your code rewritten according to the style conventions:

      while (pos != 0 && array[pos].compareTo(array[pos / 2]) < 0) {
          temp = array[pos / 2];
          array[pos / 2] = array[pos];
          array[pos] = temp;
          pos /= 2;
      }
      
    • Blank lines: a lot of blank lines inside one method don't look good, in my opinion. They can be used for separating different logical blocks of code from each other(but in this case it might be better to create two separate methods instead), but they are definitely redundant in small methods(which is the case here).

    • In general, it is possible to make your code more concise by using the Java standard library. For instance, you can use an Arrays.copyOf method instead of the expandArray. But I believe that it is fine here because it is an exercise, not a production code(otherwise, you could have just used a PriorityQueue, but that's obviously not what you want in this case).

  5. You should write doc comments for all public classes and methods.

1
source | link

  1. The API of your class: in my opinion, there should be one more method: getMin that returns the minimum element but not removes it. The only way to get it now without deleting is to call deleteMin and then re-insert it into the heap, which is not convenient and inefficient.

  2. There is a bug in the deleteMin method. The fact that pos * 2 + 1 is less than size does not imply that pos * 2 + 2. It can lead to a NullPointerException. I have written a simple unit test that exposes the problem:

    import org.junit.Test;
    
    import static org.junit.Assert.*;
    
    public class HeapTest {
    
        @Test
        public void testDelete() throws Exception {
            Heap<String> aHeap = new Heap<String>();
            aHeap.insert("a");
            aHeap.insert("b");
            aHeap.insert("c");
            assertEquals("a", aHeap.deleteMin());
        }
    }
    

    You should always test your code in a systematic manner. Unit tests are a good way to do it. They will help you to find and fix bugs and to make sure that it works properly(but not to prove its correctness, of course). They will increase maintainability and reliability of your code. You should write unit tests for all public methods. Do not forget to test edge cases(deleting an element from an empty heap and so on).

  3. You expand an array when necessary, but you never shrink it. It can lead to a big memory overhead. For example, if we insert a lot elements into the heap and then remove most of them, the array will not shrink, consuming much more memory than necessary. You can fix it by either adding a shrinkArray method or by using a List instead of an array here. An ArrayList can handle all required operations for you. So I would use it, unless you decided not to use a List on purpose as an exercise. If it is the case, I'd still recommend creating another class that implements the List interface(or provides a similar functionality) to decouple a heap from a dynamic array. It will make your code more readable, flexible(what if you decide to change the implementation of a dynamic array one day?) and testable.

  4. Code style:

    • It is conventional to surround binary operators with whitespaces. There should also a whitespace between an if, for or while keyword and an opening parenthesis. Here is a small piece of your code rewritten according to the style conventions:

      while (pos != 0 && array[pos].compareTo(array[pos / 2]) < 0) {
          temp = array[pos / 2];
          array[pos / 2] = array[pos];
          array[pos] = temp;
          pos /= 2;
      }
      
    • Blank lines: a lot of blank lines inside one method don't look good, in my opinion. They can be used for separating different logical blocks of code from each other(but in this case it might be better to create two separate methods instead), but they are definitely redundant in small methods(which is the case here).

    • In general, it is possible to make your code more concise by using the Java standard library. For instance, you can use an Arrays.copyOf method instead of the expandArray. But I believe that it is fine here because it is an exercise, not a production code(otherwise, you could have just used a PriorityQueue, but that's obviously not what you want in this case).

  5. You should write doc comments for all public classes and methods.

Summary:

To improve you code, you can do the following:

  1. Write unit-tests.

  2. Write doc comments.

  3. Adhere to the code style conventions.

  4. Design classes in such a way that one class is responsible for one concern.