考慮以下操作
Build(A[1 . . . n])：用重復的（可能未排序的）陣列 A 的元素初始化資料結構。它在 O(n) 時間內運行。
Insert(x)：將元素x插入到資料結構中。它以 O(log n) 的時間運行。
中值：回傳當前存盤元素的中值 1。它在 O(1) 時間內運行。
我如何描述一個資料結構，即提供一個我將在這個資料結構中維護的不變數？如何撰寫 Build()、Insert() 和 Median() 的偽代碼？
更新
構建最大堆/最小堆：
void build_maxheap (int Arr[ ])
{
for(int i = N/2 ; i >= 1 ; i-- )
{
max_heapify (Arr, i) ;
}
}
void build_minheap (int Arr[ ])
{
for( int i = N/2 ; i >= 1 ; i--)
min_heapify (Arr, i);
}
這都將在 O(n) 中運行。
插入：
void insert (int Arr[ ], int val)
{
length = length 1;
Arr[ length ] = -1;
increase_val (Arr, length, val);
}
這將在 O(log n) 中運行。
中位數呢？運行時間 O(1)
uj5u.com熱心網友回復：
構建：使用中位數的中位數在 O(n) 中找到初始中位數，用它來將值分成兩半。具有較小值的一半進入最大堆，具有較大值的一半進入最小堆，每次構建時間為 O(n)。我們將保持兩個堆一樣大或最多相差一個元素。
中位數：較大堆的根，或兩個根的均值（如果堆具有相同的大小）。
插入：插入較大的堆中，然后彈出其根并插入較小的堆中。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/321842.html
上一篇：采樣xy平面中的螺旋
下一篇：攤銷分析是否僅適用于資料結構？