Heap Sort
Heap Sort
最清新的讲解 https://www.youtube.com/watch?v=t0Cq6tVNRBA
Heap sort的数据结构是BS, 为了操作方便，会将BS flattened成一个一维数组。
1
2 3
4 5 6 7
坐标如上，
getLeftChildIndex(index) {return 2*index+1;}
getRightChildIndex(index) {return 2*index+2;}
getParent(index) {return (index-1) / 2}
每一次的insertion 会发生在the end of arrary, which is BS中的第一个available 的叶子节点。然后根据条件选择是否heapifyUp, 因此insertion的复杂度为O(log(n))
每一次的deletion 是先delete 该node，然后将最后的叶子节点也就是the end of array 摆放到被delete掉的节点的位置。然后根据条件选择是否heapifyDown. 因此，deletion的复杂度也为O(log(n))
最清新的讲解 https://www.youtube.com/watch?v=t0Cq6tVNRBA
Heap sort的数据结构是BS, 为了操作方便，会将BS flattened成一个一维数组。
1
2 3
4 5 6 7
坐标如上，
getLeftChildIndex(index) {return 2*index+1;}
getRightChildIndex(index) {return 2*index+2;}
getParent(index) {return (index-1) / 2}
每一次的insertion 会发生在the end of arrary, which is BS中的第一个available 的叶子节点。然后根据条件选择是否heapifyUp, 因此insertion的复杂度为O(log(n))
每一次的deletion 是先delete 该node，然后将最后的叶子节点也就是the end of array 摆放到被delete掉的节点的位置。然后根据条件选择是否heapifyDown. 因此，deletion的复杂度也为O(log(n))
Comments
Post a Comment