文心一言 VS 訊飛星火 VS chatgpt （64）-- 算法導論6.5 3題

三、要求用最小堆實現(xiàn)最小優(yōu)先隊列，請寫出 HEAP-MINIMUM、HEAP-EXTRACT-MIN、HEAP DECREASE-KEY 和 MIN-HEAP-INSERT 的偽代碼。

文心一言：

以下是使用最小堆實現(xiàn)最小優(yōu)先隊列的 HEAP-MINIMUM、HEAP-EXTRACT-MIN、HEAP-DECREASE-KEY 和 MIN-HEAP-INSERT 的偽代碼：

//?初始化最小堆??
min_heap?=?[]??
??
//?插入元素到最小堆??
def?min_heap_insert(element):??
????min_heap.append(element)??
????//?將新元素上移直到其滿足堆的性質(zhì)??
????heapify_up(len(min_heap)?-?1)??
??
//?提取最小元素并保持最小堆性質(zhì)??
def?min_heap_extract_min():??
????if?len(min_heap)?==?0:??
????????return?None??
????if?len(min_heap)?==?1:??
????????return?min_heap.pop()??
????min_value?=?min_heap[0]??
????min_heap[0]?=?min_heap.pop()??
????heapify_down(0)??
????return?min_value??
??
//?修改元素值并保持最小堆性質(zhì)??
def?min_heap_decrease_key(element,?new_value):??
????min_heap[min_heap.index(element)]?=?new_value??
????heapify_up(min_heap.index(element))??
??
//?上移元素直到其滿足堆的性質(zhì)??
def?heapify_up(index):??
????parent_index?=?(index?-?1)?//?2??
????if?parent_index?>=?0?and?min_heap[index]?<?min_heap[parent_index]:??
????????min_heap[index],?min_heap[parent_index]?=?min_heap[parent_index],?min_heap[index]??
????????heapify_up(parent_index)??
??
//?下移元素直到其滿足堆的性質(zhì)??
def?heapify_down(index):??
????left_child_index?=?2?*?index?+?1??
????right_child_index?=?2?*?index?+?2??
????min_child_index?=?index??
????if?left_child_index?<?len(min_heap)?and?min_heap[left_child_index]?<?min_heap[min_child_index]:??
????????min_child_index?=?left_child_index??
????if?right_child_index?<?len(min_heap)?and?min_heap[right_child_index]?<?min_heap[min_child_index]:??
????????min_child_index?=?right_child_index??
????if?min_child_index?!=?index:??
????????min_heap[index],?min_heap[min_child_index]?=?min_heap[min_child_index],?min_heap[index]??
????????heapify_down(min_child_index)

這些函數(shù)實現(xiàn)了最小優(yōu)先隊列的基本操作。其中，min_heap_insert 插入元素到最小堆中，min_heap_extract_min 提取最小元素并保持最小堆性質(zhì)，min_heap_decrease_key 修改元素值并保持最小堆性質(zhì)，heapify_up 和 heapify_down 分別是上移和下移元素直到其滿足堆的性質(zhì)的輔助函數(shù)。

訊飛星火：

1. 1.?HEAP-MINIMUM 偽代碼：function?HEAP_MINIMUM(heap,?size):
?if?size?==?0:
?????return?None
?minValue?=?heap[0]
?for?i?in?range(1,?size):
?????if?heap[i]?<?minValue:
?????????minValue?=?heap[i]
?return?minValue

2. 2.?HEAP-EXTRACT-MIN 偽代碼：function?HEAP_EXTRACT_MIN(heap,?size):
?if?size?==?0:
?????return?None
?minValue?=?heap[0]
?maxIndex?=?0
?for?i?in?range(1,?size):
?????if?heap[i]?<?minValue:
?????????minValue?=?heap[i]
?????????maxIndex?=?i
?if?maxIndex?!=?0:
?????heap[0],?heap[maxIndex]?=?heap[maxIndex],?heap[0]
?????HEAP_DECREASE_KEY(heap,?maxIndex,?minValue)
?return?minValue

3. 3.?HEAP DECREASE-KEY 偽代碼：function?HEAP_DECREASE_KEY(heap,?index,?newValue):
?while?index?>?0?and?heap[(index?-?1)?//?2]?>?newValue:
?????heap[(index?-?1)?//?2]?=?heap[index]
?????index?=?(index?-?1)?//?2
?HEAP_STORE(heap,?index,?newValue)

4. 4.?MIN-HEAP-INSERT 偽代碼：function?MIN_HEAP_INSERT(heap,?size,?value):
?if?size?==?heap.length:
?????heap?=?resizeArray(heap,?size?*?2)
?i?=?size
?HEAP_STORE(heap,?i,?value)
?j?=?i
?while?j?>?0?and?HEAP_EXTRACT_MIN(heap,?j)?>?value:
?????HEAP_STORE(heap,?j,?heap[(j?-?1)?//?2])
?????j?=?(j?-?1)?//?2

360智腦：

HEAP-MINIMUM(root):

if?root?is?empty?or?root.key?==?minimumKey:?

????return?None?

minNode?=?heap[0]?

heap.pop()?

return?minNode?

HEAP-EXTRACT-MIN(root):

if?root?is?None:?

????return?None?

minNode?=?root?

heap.insert(root)?

return?minNode?

HEAP DECREASE-KEY(root):

if?root?is?None:?

????return?None?

minNode?=?root?

while?minNode.right:?

????minNode?=?minNode.right?

????heap.decreaseKey(minNode.right)?

heap.decreaseKey(minNode)?

return?minNode?

MIN-HEAP-INSERT(root):

if?root?is?None:?

????return?None?

minNode?=?root?

while?not?minNode.left?and?not?minNode.right:?

????minNode?=?minNode.left?

????heap.insert(minNode)?

heap.decreaseKey(minNode)?

return?minNode

chatglm：

以下是使用最小堆實現(xiàn)最小優(yōu)先隊列的偽代碼：

HEAP-MINIMUM(heap,?n):??
???//?在最小堆中找到最小的元素??
???//?heap?是堆，n?是元素個數(shù)??
???i?←?n/2??
???if?i?<?0?then?return?null??
???j?←?2*i??
???if?j?<?n?and?heap[j]?<?heap[i]?then?i?←?j??
???if?j?<?n?and?heap[j+1]?<?heap[i]?then?i?←?j+1??
???return?heap[i]
HEAP-EXTRACT-MIN(heap,?n):??
???//?從最小堆中取出最小的元素??
???//?heap?是堆，n?是元素個數(shù)??
???result?←?HEAP-MINIMUM(heap,?n)??
???if?result?==?null?then?return?null??
???for?i?←?n-1?downto?1:??
???????heap[i]?←?heap[i+1]??
???heap[n]?←?null??
???return?result
HEAP-DECREASE-KEY(heap,?n,?i):??
???//?減小堆中第?i?個元素的優(yōu)先級??
???//?heap?是堆，n?是元素個數(shù)，i?是元素索引??
???if?i?<?0?or?i?>=?n?then?return??
???j?←?2*i??
???if?j?<?n?and?heap[j]?>=?heap[i]?then?return??
???heap[i]?←?heap[j]??
???HEAP-DECREASE-KEY(heap,?n,?j)
MIN-HEAP-INSERT(heap,?n,?key):??
???//?將元素?key?插入最小堆中，返回新的元素個數(shù)??
???//?heap?是堆，n?是元素個數(shù)，key?是元素值??
???if?n?==?0?then??
???????heap?←?[key]??
???????n?←?1??
???????return?1??
???i?←?n/2??
???if?key?<?heap[i]?then?i?←?1??
???heap[i]?←?key??
???HEAP-DECREASE-KEY(heap,?n,?i)??
???return?n??

這些偽代碼函數(shù)可以通過編程語言的堆實現(xiàn)來實現(xiàn)最小優(yōu)先隊列。在這些函數(shù)中，HEAP-MINIMUM 函數(shù)用于在堆中查找最小元素，HEAP-EXTRACT-MIN 函數(shù)用于從堆中提取最小元素，HEAP-DECREASE-KEY 函數(shù)用于減小堆中某個元素的優(yōu)先級，MIN-HEAP-INSERT 函數(shù)用于將元素插入到最小堆中并返回新的元素個數(shù)。使用這些函數(shù)，可以實現(xiàn)最小優(yōu)先隊列的插入、刪除和查找操作。

通義千問：

下面是最小堆常用操作的偽代碼：

HEAP-MINIMUM: 對堆頂元素進行比較，如果比堆底元素小，則將堆底元素替換為堆頂元素；否則，保持堆頂元素不變。

HEAP-EXTRACT-MIN: 取出堆頂元素，并將堆頂元素的父節(jié)點（如果存在）移動至其子節(jié)點中最小的一個。如果堆頂元素沒有子節(jié)點，則將堆底元素移動至堆頂，并將堆底元素的父節(jié)點（如果存在）移動至其子節(jié)點中最小的一個。

HEAP-DECREASE-KEY: 對堆頂元素的鍵值進行比較，如果比堆底元素的鍵值小，則將堆底元素替換為堆頂元素；否則，保持堆頂元素不變。

MIN-HEAP-INSERT: 將元素插入堆中，并檢查插入后的堆是否滿足最小堆的性質(zhì)。如果不滿足，則對堆進行調(diào)整，直到滿足最小堆的性質(zhì)為止。

天工：

下面是使用最小堆實現(xiàn)最小優(yōu)先隊列的偽代碼：

HEAP-MINIMUM：

1.如果堆為空，則返回 -1；

2.否則，取出堆頂元素 x，如果 x 大于等于 key，則返回 x；

3.否則，執(zhí)行下面的步驟，直到找到一個元素 x 滿足條件 x 大于等于 key：

a. 取出堆頂元素 y，將 y 替換為 x；

b. 執(zhí)行 HEAP-EXTRACT-MIN。

HEAP-EXTRACT-MIN：

1.如果堆為空，則返回 -1；

2.否則，取出堆頂元素 x，將 x 替換為堆頂元素 y，并將 y 刪除；

3.執(zhí)行下面的步驟，直到堆為空：

a. 執(zhí)行 HEAP-DECREASE-KEY。

HEAP-DECREASE-KEY：

1.如果堆為空，則返回 -1；

2.否則，取出堆頂元素 x，將 x 替換為堆頂元素 x 的下一個元素 y；

3.執(zhí)行下面的步驟，直到堆為空：

a. 執(zhí)行 HEAP-EXTRACT-MIN。

MIN-HEAP-INSERT：

1.如果堆為空，則將元素 x 插入堆中；

2.否則，取出堆頂元素 x，將元素 x 插入堆中，并將元素 x 替換為堆頂元素 y；

3.執(zhí)行下面的步驟，直到堆中只有一個元素：

a. 執(zhí)行 HEAP-EXTRACT-MIN。

chatgpt：

以下是使用最小堆實現(xiàn)最小優(yōu)先隊列的偽代碼：

HEAP-MINIMUM(A): 返回 A[0] // A[0] 是最小堆中的最小元素

HEAP-EXTRACT-MIN(A): 如果 A.length < 1: 返回 錯誤（堆為空） min = A[0] // 最小元素為根節(jié)點 A[0] = A[A.length - 1] // 將最后一個元素放到根節(jié)點 A.length = A.length - 1 // 去除最后一個元素 MIN-HEAPIFY(A, 0) // 保持最小堆的性質(zhì) 返回 min

HEAP-DECREASE-KEY(A, i, key): 如果 key > A[i]: 返回 錯誤（新的鍵值大于當前鍵值） A[i] = key // 更新鍵值 while i > 0 并且 A[PARENT(i)] > A[i]: // 如果父節(jié)點的鍵值大于當前節(jié)點的鍵值 交換 A[i] 和 A[PARENT(i)] // 交換節(jié)點和其父節(jié)點 i = PARENT(i) // 上移節(jié)點，繼續(xù)檢查

MIN-HEAP-INSERT(A, key): A.length = A.length + 1 // 擴展堆的容量 A[A.length - 1] = +∞ // 將新節(jié)點設(shè)置為正無窮大 HEAP-DECREASE-KEY(A, A.length - 1, key) // 更新節(jié)點鍵值，保持最小堆的性質(zhì)

其中，PARENT(i) 返回節(jié)點索引 i 的父節(jié)點索引，MIN-HEAPIFY(A, i) 用于保持最小堆的性質(zhì)，將節(jié)點 i 向下調(diào)整以滿足最小堆的條件。

總結(jié)