温馨提示×

Python TreeNode如何实现树的堆排序

小樊
84
2024-08-17 16:25:40
栏目: 编程语言

实现树的堆排序可以使用Python中的TreeNode类来表示树节点,同时使用堆排序算法来对树进行排序。以下是一个示例代码:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def heapify(root, size, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    
    if l < size and root[l].val > root[largest].val:
        largest = l
    
    if r < size and root[r].val > root[largest].val:
        largest = r
    
    if largest != i:
        root[i], root[largest] = root[largest], root[i]
        heapify(root, size, largest)

def heap_sort(root):
    size = len(root)
    
    for i in range(size//2 - 1, -1, -1):
        heapify(root, size, i)
    
    for i in range(size-1, 0, -1):
        root[i], root[0] = root[0], root[i]
        heapify(root, i, 0)
    
    return root

# 示例
root = [TreeNode(4), TreeNode(10), TreeNode(7), TreeNode(5), TreeNode(1)]

sorted_root = heap_sort(root)

for node in sorted_root:
    print(node.val)

在上面的代码中,我们首先定义了TreeNode类来表示树节点,然后实现了heapify函数来维护堆的性质,以及heap_sort函数来对树进行堆排序。最后我们通过示例代码对一个树节点列表进行堆排序,并输出排序后的结果。

0