Heap sort, index of array starting at index 1

Question

# To heapify subtree rooted at index i.
def maxHeapify(list, heapSize, i):
    largest = i
    leftChild = 2 * i 
    rightChild = 2 * i + 1
    while leftChild < heapSize and list[largest] < list[leftChild]:
        largest = leftChild
    while rightChild < heapSize and list[largest] < list[rightChild]:
        largest = rightChild
    if largest != i:
        list[i], list[largest] = list[largest], list[i]
        maxHeapify(list, heapSize, largest)

def heapSort(list):

    heapSize = len(list)
    for i in range(heapSize//2, 0, -1):
        maxHeapify(list, heapSize, i)
    for i in range(heapSize, 0, -1):
        list[i], list[1] = list[1], list[i]
        maxHeapify(list, i, 1)

list = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heapSort(list)
print("Sorted array is: ")
for i in range(len(list)):
    print(list[i], end=" ")

Since the index array starts from 1 in heap sort, I have solved this problem in this way. But I am getting an error "IndexError: list index out of range." It would be nice if anyone would help me to find out the bug of this code. I have attached a picture below of the output I got.

output

for i in range(heapSize, 0, -1): starts with i = heapSize, but heapSize is not a valid index into the list, because a list in python is indexed starting at 0, ending at heapSize-1. — user3386109
– user3386109, Commented Nov 18, 2021 at 9:12

trincot · Accepted Answer · 2021-11-18 09:52:30Z

1

The error occurs because list[i] is an invalid reference when i is heapSize.

Some issues:

The last loop in heapSort is not part of the standard algorithm of heap sort. It apparently swaps all elements with what is at index 1. If this was intended to map the list from an index-1 arrangement to a index-0 arrangement, it is not the right way to do so.
Although it is not breaking the algorithm in practice, the heapify function should not have a while construct. Those two while blocks should be if blocks.
Don't use the name list for your list as it refers to the type.

Since the index array starts from 1 in heap sort...

There is no rule that heap sort needs to start with index 1. Trying to work with an index 1 based array instead of 0 is unnatural in Python, as your list really has data at index 0 and not at index heapSize. So just convert your algorithm to be 0-index based:

def maxHeapify(lst, heapSize, i):  # Name list is already used. Use different name
    largest = i
    leftChild = 2 * i + 1  # Use logic corresponding to 0-based index
    rightChild = leftChild + 1
    # no while-loops here!
    if leftChild < heapSize and lst[largest] < lst[leftChild]:
        largest = leftChild
    if rightChild < heapSize and lst[largest] < lst[rightChild]:
        largest = rightChild
    if largest != i:
        lst[i], lst[largest] = lst[largest], lst[i]
        maxHeapify(lst, heapSize, largest)

def heapSort(lst):
    heapSize = len(lst)
    for i in range((heapSize - 1) // 2, -1, -1): # Adapted to 0-based index
        maxHeapify(lst, heapSize, i)
    # The part you had at this spot is not good: leave it out

answered Nov 18, 2021 at 9:52

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Sudipta Bhatta Over a year ago

What will the part in the for loop you mentioned is not good? I am a bit confused about that part. Therefore, I didn't get the correct output yet.

trincot Over a year ago

You mention two things: (1) why that removed loop is not good? -- because it is not in any standard implementation. Swapping any other index with index 1 makes no sense. Could you explain to me why you thought you needed to do that? (2) You say you don't get the correct output. Can you please provide an example of input & wrong output?

Sudipta Bhatta Over a year ago

Now I have rewritten the code with index 0, as you said, it is unnecessary to start indexing with 1. (1) The loop you are saying to remove, I needed to do that because I want to sort the numbers in ascending order in heapsort. (2) After indexing with 0, I got the correct output. But, I do not understand how the maxHeapify() function of the for loop works in the last line that you said to remove. Example: for i in range(heapSize-1, -1, -1): arr[i], arr[0] = arr[0], arr[i] maxHeapify(arr, i, 0)

trincot Over a year ago

If you need to sort in ascending order, then the loop you had will not help. Just use the reverse method. Or use a min-heap instead of a max-heap. (2) I don't know what you mean with "after indexing with 0". I don't see anything in your question's driver code that does it somehow differently. I don't understand your last question -- it seems quite broad. Are you saying you don't understand how the heapify function works? Have you checked Wikipedia?

trincot Over a year ago

Did this answer your question?

Collectives™ on Stack Overflow

Heap sort, index of array starting at index 1

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related