Lua Program to Implement Heap Sort

Lua Program to Implement Heap Sort

Leave a Comment • • Algorithm Example, Algorithm Implementation, Beginner Guide, Code Tutorial, Data Structures, Heap Sort, Learn Lua, Lua, Lua Programming, Sorting Algorithm, Sorting Algorithms, Sorting Example

Heap Sort is a powerful and reliable sorting algorithm that is often taught after simpler sorts like Bubble Sort and Selection Sort. It is based on a special data structure called a heap, which helps us always pick the largest or smallest value efficiently. When learning algorithms, Heap Sort matters because it shows how data structures and sorting techniques work together to solve problems in a smart way.

In real life, Heap Sort is useful when you want good performance and predictable behavior. Unlike some other fast sorting methods, Heap Sort always runs in the same time complexity, even in the worst case. This makes it useful in systems programming, priority-based scheduling, and situations where stable performance is more important than simplicity. In this article, you will learn how to implement Heap Sort in Lua step by step, using clear and beginner-friendly programs.

Program 1: Basic Heap Sort using loops

This program shows the most common way to implement Heap Sort in Lua using loops and helper functions. It uses predefined data so you can run it directly and see the output. This version is perfect for beginners who want to understand the standard approach.

-- Heap Sort in Lua using loops

function heapify(arr, n, i)

    local largest = i
    local left = 2 * i
    local right = 2 * i + 1

    if left <= n and arr[left] > arr[largest] then
        largest = left
    end

    if right <= n and arr[right] > arr[largest] then
        largest = right
    end

    if largest ~= i then
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    end

end

function heapSort(arr)

    local n = #arr

    for i = math.floor(n / 2), 1, -1 do
        heapify(arr, n, i)
    end

    for i = n, 2, -1 do
        arr[1], arr[i] = arr[i], arr[1]
        heapify(arr, i - 1, 1)
    end

end

local numbers = {12, 11, 13, 5, 6, 7}
heapSort(numbers)

for i = 1, #numbers do
    io.write(numbers[i] .. " ")
end

This program works by first turning the array into a max heap, where the largest value is always at the top. After that, the largest value is swapped to the end of the array, and the heap size is reduced. Beginners can understand this by thinking of it as repeatedly picking the biggest number and placing it in its correct position.

Program 2: Heap Sort with clear helper functions

This version separates the logic into smaller helper functions to make the code easier to read. It is helpful for beginners who want clean and readable Lua programs.

-- Heap Sort with helper functions

function buildHeap(arr, n)

    for i = math.floor(n / 2), 1, -1 do
        heapify(arr, n, i)
    end

end

function heapify(arr, n, i)

    local largest = i
    local left = 2 * i
    local right = 2 * i + 1

    if left <= n and arr[left] > arr[largest] then
        largest = left
    end

    if right <= n and arr[right] > arr[largest] then
        largest = right
    end

    if largest ~= i then
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    end

end

function heapSort(arr)

    local n = #arr
    buildHeap(arr, n)

    for i = n, 2, -1 do
        arr[1], arr[i] = arr[i], arr[1]
        heapify(arr, i - 1, 1)
    end

end

local data = {20, 3, 15, 7, 9, 1}
heapSort(data)

for _, value in ipairs(data) do
    io.write(value .. " ")
end

This program does the same job as the first one, but the steps are easier to follow. By separating heap creation from sorting, beginners can understand how each part contributes to the final result. This style is very useful when writing larger programs.

Program 3: Heap Sort using recursion clearly

This program highlights the recursive nature of Heap Sort more clearly. While recursion is already used in heapify, this example focuses on understanding recursive calls step by step.

-- Heap Sort focusing on recursion

function heapify(arr, size, root)

    local largest = root
    local left = root * 2
    local right = root * 2 + 1

    if left <= size and arr[left] > arr[largest] then
        largest = left
    end

    if right <= size and arr[right] > arr[largest] then
        largest = right
    end

    if largest ~= root then
        arr[root], arr[largest] = arr[largest], arr[root]
        heapify(arr, size, largest)
    end

end

function heapSort(arr)

    local size = #arr

    for i = math.floor(size / 2), 1, -1 do
        heapify(arr, size, i)
    end

    for i = size, 2, -1 do
        arr[1], arr[i] = arr[i], arr[1]
        heapify(arr, i - 1, 1)
    end

end

local values = {9, 4, 8, 3, 1, 2}
heapSort(values)

for i = 1, #values do
    print(values[i])
end

This approach is useful for learners who want to get comfortable with recursion in Lua. Understanding how heapify calls itself helps you see how the heap property is maintained automatically. Once this idea clicks, many other algorithms become easier to learn.

Program 4: Heap Sort with step-by-step output

This version prints intermediate results so beginners can see how the array changes during sorting. It is very helpful for learning and debugging.

-- Heap Sort with step-by-step output

function heapify(arr, n, i)

    local largest = i
    local left = 2 * i
    local right = 2 * i + 1

    if left <= n and arr[left] > arr[largest] then
        largest = left
    end

    if right <= n and arr[right] > arr[largest] then
        largest = right
    end

    if largest ~= i then
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    end

end

function heapSort(arr)

    local n = #arr

    for i = math.floor(n / 2), 1, -1 do
        heapify(arr, n, i)
    end

    for i = n, 2, -1 do

        arr[1], arr[i] = arr[i], arr[1]

        print("After swap:")

        for _, v in ipairs(arr) do
            io.write(v .. " ")
        end

        print()

        heapify(arr, i - 1, 1)

    end

end

local sample = {14, 10, 8, 7, 9, 3}
heapSort(sample)

By printing the array after each swap, beginners can visually follow the sorting process. This makes Heap Sort feel less abstract and more understandable. It is especially useful when learning how heaps change over time.

Program 5: Heap Sort in descending order

This program modifies Heap Sort slightly to sort numbers in descending order. It shows how flexible the algorithm can be.

-- Heap Sort for descending order

function heapifyMin(arr, n, i)

    local smallest = i
    local left = 2 * i
    local right = 2 * i + 1

    if left <= n and arr[left] < arr[smallest] then
        smallest = left
    end

    if right <= n and arr[right] < arr[smallest] then
        smallest = right
    end

    if smallest ~= i then
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapifyMin(arr, n, smallest)
    end

end

function heapSortDescending(arr)

    local n = #arr

    for i = math.floor(n / 2), 1, -1 do
        heapifyMin(arr, n, i)
    end

    for i = n, 2, -1 do
        arr[1], arr[i] = arr[i], arr[1]
        heapifyMin(arr, i - 1, 1)
    end

end

local nums = {5, 12, 7, 3, 9}
heapSortDescending(nums)

for _, num in ipairs(nums) do
    io.write(num .. " ")
end

This version uses a min heap instead of a max heap. Beginners can learn from this that sorting order depends on how you compare values. It also shows how small changes in logic can give different results.

Program 6: Heap Sort handling negative and floating-point numbers

Heap Sort works naturally with negative and floating-point numbers in Lua, but this program makes it clear by using such data. This helps beginners feel confident about real-world usage.

-- Heap Sort with negative and floating-point numbers

function heapify(arr, n, i)

    local largest = i
    local left = 2 * i
    local right = 2 * i + 1

    if left <= n and arr[left] > arr[largest] then
        largest = left
    end

    if right <= n and arr[right] > arr[largest] then
        largest = right
    end

    if largest ~= i then
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    end

end

function heapSort(arr)

    local n = #arr

    for i = math.floor(n / 2), 1, -1 do
        heapify(arr, n, i)
    end

    for i = n, 2, -1 do
        arr[1], arr[i] = arr[i], arr[1]
        heapify(arr, i - 1, 1)
    end

end

local mixed = {3.5, -2.1, 4.8, 0, -7.3, 1.2}
heapSort(mixed)

for _, v in ipairs(mixed) do
    io.write(v .. " ")
end

This final example shows that Heap Sort in Lua does not need special changes to handle negative or decimal values. Lua compares numbers naturally, so the algorithm works as expected. Beginners can use this confidently in real programs with mixed numeric data.

Frequently Asked Questions (FAQ)

This section answers common beginner questions about Heap Sort in Lua and clears up common confusion.

Q1. Is Heap Sort faster than Bubble Sort in Lua?
Yes, Heap Sort is much faster for large datasets because it uses a better time complexity. Bubble Sort is easier to learn but not practical for big inputs.

Q2. Is Heap Sort stable?
No, Heap Sort is not a stable sorting algorithm. This means equal elements might change their original order.

Q3. Does Heap Sort need extra memory?
Heap Sort works in place, which means it does not need extra arrays. This makes it memory efficient.

Q4. Can Heap Sort be used in real applications?
Yes, Heap Sort is used in priority queues, scheduling systems, and performance-critical applications.

Q5. Is Heap Sort hard for beginners?
It may look complex at first, but with practice and step-by-step programs, beginners can understand it well.

Conclusion

Heap Sort is an important sorting algorithm that every beginner should learn after understanding simpler sorts. In this article, you explored multiple Lua programs that implement Heap Sort in different ways, from basic loops to recursive approaches and even handling negative and floating-point numbers. Each example showed how the algorithm works and why it is useful.

By practicing these Lua programs and running them with different data, you can build strong confidence in sorting algorithms. Keep experimenting, stay curious, and try comparing Heap Sort with other algorithms to deepen your understanding. With time and practice, these concepts will feel natural and powerful.

Recommended Courses

Related Posts

Scroll to Top