Python Forum
Is my heap sort optimized?
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Is my heap sort optimized?
#1
It's been a long time since I made my first heap sort algorithm.
I'm looking for optimization tips for this one that I put together this morning.
def get_children(index):
    l_child = index * 2
    return l_child, l_child + 1

def get_lesser_child(heap, index):
    l_child, r_child = get_children(index)
    lesser = None
    size = len(heap)
    if l_child < size:
        lesser = l_child
        if r_child < size and heap[r_child] < heap[l_child]:
            lesser = r_child
    return lesser

def swap(heap, index_a, index_b):
    heap[index_a], heap[index_b] = heap[index_b], heap[index_a]

def sift(heap, high_index):
    low_index = 1
    lesser_child = get_lesser_child(heap, low_index)
    while lesser_child and heap[low_index] > heap[lesser_child]:
        swap(heap, low_index, lesser_child)
        low_index = lesser_child
        lesser_child = get_lesser_child(heap, low_index)

def heapify(heap):
    for high_index in range(len(heap) - 1, 0, -1):
        swap(heap, 1, high_index)
        sift(heap, high_index)

heap = [None, 8, 6, 7, 5, 3, 0, 9]
heapify(heap)
print(heap)


Output:
[None, 0, 3, 6, 5, 9, 7, 8]
I'm thinking about using the new 3.8 walrus in the sift function:

def sift(heap, high_index):
    low_index = 1
    while (lesser_child := get_lesser_child(heap, low_index)) and heap[low_index] > heap[lesser_child]:
        swap(heap, low_index, lesser_child)
        low_index = lesser_child
Has anyone used it? Is it faster?
Reply
#2
Looks like the walrus is slower, at least the way that I'm using and timing it.
import time
import random

def get_children(index):
    l_child = index * 2
    return l_child, l_child + 1

def get_lesser_child(heap, index):
    l_child, r_child = get_children(index)
    lesser = None
    size = len(heap)
    if l_child < size:
        lesser = l_child
        if r_child < size and heap[r_child] < heap[l_child]:
            lesser = r_child
    return lesser

def swap(heap, index_a, index_b):
    heap[index_a], heap[index_b] = heap[index_b], heap[index_a]

def sift(heap, high_index):
    low_index = 1
    lesser_child = get_lesser_child(heap, low_index)
    while lesser_child and heap[low_index] > heap[lesser_child]:
        swap(heap, low_index, lesser_child)
        low_index = lesser_child
        lesser_child = get_lesser_child(heap, low_index)

def sift_w(heap, high_index):
    low_index = 1
    while (lesser_child := get_lesser_child(heap, low_index)) and heap[low_index] > heap[lesser_child]:
        swap(heap, low_index, lesser_child)
        low_index = lesser_child

def heapify(heap):
    for high_index in range(len(heap) - 1, 0, -1):
        swap(heap, 1, high_index)
        sift(heap, high_index)

def heapify_w(heap):
    for high_index in range(len(heap) - 1, 0, -1):
        swap(heap, 1, high_index)
        sift_w(heap, high_index)

list_size = 1000000
print("Making random list")
rand_list = []
for count in range(list_size):
    rand_list.append(random.randint(0,99999999))

rand_list.insert(0, None)

print("Running carpenter version")
heap = rand_list.copy()
start = time.time()
heapify(heap)
end = time.time()
print(end - start)

print("Running walrus version")
heap = rand_list.copy()
start = time.time()
heapify_w(heap)
end = time.time()
print(end - start)
Output:
Making random list Running carpenter version 3.514843702316284 Running walrus version 3.530456781387329 >>> = RESTART: Making random list Running carpenter version 3.8112730979919434 Running walrus version 3.89424705505371 >>>
Reply


Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020