堆(Heap) 12 ① TheMAX-HEAPIFYrocedure,which runs in O(lg n)time,is the key to main- 10 ⑤ faining the max-heap property. The BUILD-MAX-HEAPprocedure,which runs in linear time,produces a max- ⑤ (① ⑩⑥ 1② heap from an unordered input array Max-heap property Min-heap property The HEAPSORT procedure,which(runs in O(n Ign)time,sorts an array in A[Parent(i】≥A[d A[Parent(i】≤A[ place. The MAX-HEAP-INSERT HEAP-EXTRACT-MAX HEAP-INCREASE-KEY, and HEAP-MAXIMUM procedures,which run in O(Ig n)time,allow the heap data structure to implement a priority queue. PARENT(i) 16 1 return Li/2] 10 ↓234567890 LEFT() 堆排序(HeapSort) 16140879324D 1 return 2i 。 实现优先队列的一种常用方式 2 RIGHT(i) (a) 1 return 2i+1
堆（Heap） • 堆排序（HeapSort） • 实现优先队列的一种常用方式
动态等价关系—并查集实现 动态等价关系 MAKE-SET(x)creates a new set whose only member (and thus representative) is x.Since the sets are disjoint,we require thatx not already be in some other set. UNION(x.y)unites the dynamic sets that contain x and y,say Sx and Sy,into a new set that is the union of these two sets.We assume that the two sets are dis- joint prior to the operation.The representative of the resulting set is any member of SxU S,although many implementations of UNION specifically choose the representative of either Sx or Sy as the new representative.Since we require the sets in the collection to be disjoint,conceptually we destroy sets S and Sy. removing them from the collection 8.In practice,we often absorb the elements of one of the sets into the other set. FIND-SET(x)returns a pointer to the representative of the (unique)set contain- ingx
动态等价关系——并查集实现 动态等价关系
动态等价关系—并查集实现 并查集-基于链表 并查集-基于根数森林 Linked-list representation of disjoint sets 操作union(g,e)执行后 (a) (b) ·MAKE-SET 。 simply creates a rooted tree with just one node ·FIND-SET follows parent pointers until finds the root of the tree. 。 UNION causes the root of one tree to point to the root of the other
动态等价关系——并查集实现 并查集-基于链表 并查集-基于根数森林 • MAKE-SET • simply creates a rooted tree with just one node. • FIND-SET • follows parent pointers until finds the root of the tree. • UNION • causes the root of one tree to point to the root of the other
动态等价关系— 并查集实现 并查集-基于根数森林 注意： MAKE-SET(x) rank如何定义与修改. 问题13： 1 x.p=x 2x.ramk=0为何用rank而不用子 树规模？ UNION(X.y) 是否可以用子树规模？ 1 LINK(FIND-SET(x).FIND-SET(y)) LINK(x.y) 1 if x.rank y.rank FIND-SET(x) (a) (b) 2 1 v.p=x ifx≠x,P 3 else x.p =y 2 x·p=FIND-SET(x.p) MAKE-SET 3 if x.rank =y.rank return x.p simply creates a rooted tree with just one node y.rank=上，ank+I ·FIND-SET follows parent pointers until finds the root of the tree rank.which is an upper bound on the height of the node ·UNION causes the root of one tree to point to the root of the other
动态等价关系——并查集实现 并查集-基于根数森林 • MAKE-SET • simply creates a rooted tree with just one node. • FIND-SET • follows parent pointers until finds the root of the tree. • UNION • causes the root of one tree to point to the root of the other
并查集的应用 连通分量 Kruskal算法 MST-KRUSKAL(G,w) 1A=0 CONNECTED-COMPONENTS(G) 2 for each vertex v∈G./ I for each vertex v G.V MAKE-SET(v) MAKE-SET(v) 4 sort the edges of G.E into nondecreasing order by weight w 3 for each edge (u.v)E G.E 5 for each edge (u,v)G.E,taken in nondecreasing order by weight 4 if FIND-SET(u)FIND-SET(v) 6 if FIND-SET(u)FIND-SET(v) 5 UNION(.V) 个 A=AU(u,v) SAME-COMPONENT(.V) UNION(,v) 9 return A 1 if FIND-SET()==FIND-SET(v) 2 return TRUE 3 else return FALSE
并查集的应用 连通分量 Kruskal算法