堆排序及代码实现
堆排序
堆的先验知识：
堆的实现通常是通过构造二叉堆实现。当不加限定时，堆通常指的就是二叉堆。
二叉堆一般分为两种：最大堆和最小堆。
最大堆： 最大堆中的最大元素在根结点（堆顶）；堆中每个父节点的元素值都大于等于其子结点；
最小堆： 最小堆中的最小元素出现在根结点（堆顶）；堆中每个父节点的元素值都小于等于其子结点。
二叉堆是一种完全二叉树，对于完全二叉树来说，只有树????的最后一层的节点不是满的，其他层都是满的，完全二叉树采用顺序存储，利用数组进行实现；
并且，父亲节点和子节点有如下关系：父亲节点的下标如果为i，则左右子节点的下标分别为2*i+ 1，2 * i + 2。
构建一个大顶堆采用下沉调整：从第一个非叶子节点开始，从右至左依次调整节点；
图如下所示：图参考自：https://www.cnblogs.com/chengxiao/p/6129630.html
第一个非叶子节点的下标为arr.length/2 - 1
代码逻辑：
对于每一个父亲节点，首先找到其左孩子的下标，然后判断是否有右孩子，如果有，比较一下左右孩子的大小，
如果由右孩子大于左孩子，
---------------则比较父亲节点和右孩子的大小（因为父亲节点要大于任何一个孩子），如果父亲节点大于右孩子（则父亲节点大于任何一个孩子），无需下沉父亲节点；否则，进行下沉；
如果右孩子小于左孩子，
--------------则比较父亲节点和左孩子的大小（因为父亲节点要大于任何一个孩子），如果父亲节点大于左孩子（则父亲节点大于任何一个孩子），无需下沉父亲节点；否则，进行下沉；
代码实现如下所示：（构建一个大根堆）
##下沉调整
def adjustHeap(self, parent_index, length):
temp = arr[parent_index]
child_index = 2 * parent_index + 1
#构建大根堆
while child_index < length:
##如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
if child_index + 1 < length and arr[child_index] < arr[child_index + 1]:
child_index += 1
#构建大根堆
#如果父节点大于任何一个孩子的值，则不进行交换，直接跳出
if arr[child_index] < temp:
break
#下面对父节点进行下沉，单向交换；
arr[parent_index] = arr[child_index]
parent_index = child_index
child_index = 2 * child_index + 1
arr[parent_index] = temp
构建一个小根堆的逻辑：
从第一个非叶子节点开始，从右向左进行调整；
找到父亲节点的左孩子，然后判断左孩子和右孩子的大小，
如果左孩子小于右孩子，
----------------则比较父亲节点和右孩子的大小，如果小于右孩子，则小于任何一个孩子节点，不进行交换，否则，进行交换；
如果左孩子大于右孩子，
---------------则比较父亲节点和左孩子的大小，如果小于左孩子，则小于任何一个孩子节点，不进行交换，否则，进行交换；
代码如下：
class Solution:
def getLeastNumbers(self, arr, k):
if k == 0:
return arr[k:k]
##下沉调整，构建一个小根堆
def adjustHeap(self, parent_index, length):
temp = arr[parent_index]
child_index = 2 * parent_index + 1
#构建小根堆
while child_index < length:
##如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
if child_index + 1 < length and arr[child_index] > arr[child_index + 1]:
child_index += 1
#构建小根堆
#如果父节点小于任何一个孩子的值，直接跳出
if temp <= arr[child_index]:
break
arr[parent_index] = arr[child_index]
parent_index = child_index
child_index = 2 * child_index + 1
arr[parent_index] = temp
堆排序
首先对于给定数组构建一个堆，如果是升序我们就构建一个大根堆；
然后交换堆顶和最后一个叶子节点的值，之后重新调整堆（不包括最后一个叶子节点），使其符合大根堆的结构；这样堆顶就是这个数组中次大的元素；
之后重复步骤二，就可以获得排序数组；
代码如下所示：
class Solution:
def getLeastNumbers(self, arr, length):
##下沉调整
def adjustHeap(self, parent_index, length):
temp = arr[parent_index]
child_index = 2 * parent_index + 1
#构建大根堆
while child_index < length:
##如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
if child_index + 1 < length and arr[child_index] < arr[child_index + 1]:
child_index += 1
#构建大根堆
#如果父节点大于任何一个孩子的值，直接跳出
if arr[child_index] < temp:
break
arr[parent_index] = arr[child_index]
parent_index = child_index
child_index = 2 * child_index + 1
arr[parent_index] = temp
# arr = [2,3,4,5,6,7,1]
#构建堆
for i in range(len(arr)//2 - 1, -1, -1):
adjustHeap(self, i, len(arr))
print(arr)
#调整堆结构
for j in range(len(arr) - 1, 0, -1):
#交换
temp1 = arr[0]
arr[0] = arr[j]
arr[j] = temp1
adjustHeap(self, 0, j)
print("#####")
print(arr)
if __name__ == '__main__':
arr = [2,3,4,5,6,7,1]
so = Solution()
so.getLeastNumbers(arr,len(arr))