Sample heap implementation does not check for nodes with one child?

136

The following code in the sample heap implementation assumes that each heap node always has two children, which seems like a bug.

Shouldn't it also handle the case when (right < realSize)?

            while (index <= realSize / 2) {
                // the left child of the deleted element
                int left = index * 2;
                // the right child of the deleted element
                int right = (index * 2) + 1;
                // If the deleted element is larger than the left or right child
                // its value needs to be exchanged with the smaller value
                // of the left and right child
                if (minHeap[index] > minHeap[left] || minHeap[index] > minHeap[right]) {
                    if (minHeap[left] < minHeap[right]) {
                        int temp = minHeap[left];
                        minHeap[left] = minHeap[index];
                        minHeap[index] = temp;
                        index = left;
                    } else {
                        // maxHeap[left] >= maxHeap[right]
                        int temp = minHeap[right];
                        minHeap[right] = minHeap[index];
                        minHeap[index] = temp;
                        index = right;
                    }
                } else {
                    break;
                }
            }

I used the following code which works (might have a typo because I have to rename some variables)

        // Loop while we're not at a leaf node.
        while( index <= (realSize / 2) )
        {
            // We're guaranteed that the left child exists, but maybe not the right child.
            int left = currentIdx * 2;
            int right = index * 2 + 1;
            
            if( (right <= realSize) && (minHeap[right] < heap[index]) && (minHeap[right] >= minHeap[left]) )
            {
                // Swap with right child
                int temp = minHeap[index];
                minHeap[current] = minHeap[right];
                minHeap[right] = temp;
            
                current = right;
            }
            else if( minHeap[left] < minHeap[current] )
            {
                // swap left child
                int temp = minHeap[index];
                minHeap[index] = minHeap[left];
                minHeap[left] = temp;
            
                index = left;
            }
            else
            {
                break;
            }
        }

Comments (0)