|----------------------------------------| | 5 | 1 | 2 | 8 | 6 | 10 | 3 | 9 | 4 | 7 | |----------------------------------------|represent a heap?
__5__ / \ / \ 1 2 / \ / \ / \ / \ 8 6 10 3 / \ / 9 4 7which is clearly not a heap.
|-----------------------| |10 | 9 | 6 | 3 | 2 | 5 | |-----------------------|Insert and remove 12. What heap results?
|----------------------------| |12 | 9 | 10 | 3 | 2 | 5 | 6 | |----------------------------|Delete(12) yields:
|------------------------| | 10 | 9 | 6 | 3 | 2 | 5 | |------------------------|(i.e., the same thing we started with).
7 5 6 4a 4.5 4b(where 4a is the first 4, and 4b is the second 4); and successive deletions give:
6 5 4b 4a 4.5 || || \||/ \/ 5 4.5 4b 4a || || \||/ \/ 4.5 4a 4b || || \||/ \/ 4b 4aso 4b will be popped before 4a.
T.TableDelete(SearchKey) I=hash(SearchKey) while (T[I] occupied and T[I].Key != SearchKey) or (T[I] deleted) I++; if (T[I] not empty) Mark T[I] deleted
|----| 0| |-->NULL |----| 1| |-->[15]-->[8] |----| 2| |-->NULL |----| 3| |-->[17]-->[24]-->[10] |----| 4| |-->[32] |----| 5| |-->NULL |----| 6| |-->NULL |----|
T.TableInsert(Key) I=hash(Key) while (T[I] occupied) ++I; T[I]=Key; T.TableRetrieve I=hash(Key) while (T[I] occupied) and (T[I]!=Key) ++I; if (T[I]==Key) return true; return false; T.Table Delete -- see STE #7.
T.TableDelete(SearchKey) I=hash(SearchKey) return T[I]->remove(Key);