Heap sort

```class Test():
def heap_sort(self, nums):
i, l = 0, len(nums)
self.nums = nums

# 构造大顶堆，从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点
for i in range(l//2-1, -1, -1):
self.build_heap(i, l-1)

print(nums)

# 上面的循环完成了大顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆
for j in range(l-1, -1, -1):
nums[0], nums[j] = nums[j], nums[0]
self.build_heap(0, j-1)

return nums

def build_heap(self, i, l):
"""构建大顶堆"""
nums = self.nums
left, right = 2*i+1, 2*i+2 ## 左右子节点的下标

large_index = i

if left <= l and nums[i] < nums[left]:
large_index = left

if right <= l and nums[left] < nums[right]:
large_index = right

# 通过上面跟左右节点比较后，得出三个元素之间较大的下标，如果较大下表不是父节点的下标，说明交换后需要重新调整大顶堆
if large_index != i:
nums[i], nums[large_index] = nums[large_index], nums[i]
self.build_heap(large_index, l)```

Is a Balanced Binary Tree

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

This problem is an easy-level at Leetcode. I probably did it more than five times, once and once again. Just like a muscle memory.

However, I found an interesting solution today, which literally changed my mind about Python…

Here is the code:

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
def isBalanced(self, root: TreeNode, h = 1) -> bool:
if not root: return h
l = self.isBalanced(root.left, h + 1)
r = self.isBalanced(root.right, h + 1)
return abs(l - r) <= 1 and max(l, r)```

I am very confused at the last line, the max(l, r) part.

I thought that max(l, r) should be converted as a bool value even it returns a integer type value, because as the second component of the operation AND, max(l, r) should represent as a bool variable.

Following by my worst idea, I supposed that the function isBalanced would return either 1 (True) or 0 (False). However, I found a crazy truth after experiments, that Python executor actually return a integer value (the maximum value of l and r) if abs(l – r) <= 1 is matched.

So, it really makes sense. Gain new knowledge of Python 🙂

Median of interval

There are two methods to calculate the median of an interval [low, high].

• m = ( l + h ) / 2
• m = l + ( h – l ) / 2

l + h may have addition overflow, but h-l will not. Therefore, it is best to use the second method of calculation.