Inserting to a heap means adding a new element to the last position, than restoring the heap property, by moving up the tree. The child of a node k in the array is at positions 2k+1 and 2k+2, so moving up the tree is just basic arithmetic.

Deleting from the heap simply means replacing the root (the element at position k 0) with the last element, delete the last element, and restore the heap property.

Without further delays, here's the code.

For insertion:

1: template <class T>

2: void addToHeap(vector<T>* heap, T val) {

` 3: heap->push_back(val);`

4: int pos = heap->size() - 1;

5: if (pos == 0)

6: return;

7: bool fixingHeap = true;

8: do {

9: int parent = 0;

10: if (pos % 2 == 0)

` 11: parent = (pos - 2) / 2;`

12: else

` 13: parent = (pos - 1) / 2;`

14: if (heap->at(parent) < heap->at(pos)) {

` 15: T temp = heap->at(pos);`

` 16: heap->at(pos) = heap->at(parent);`

` 17: heap->at(parent) = temp;`

` 18: pos = parent;`

19: } else {

20: fixingHeap = false;

` 21: }`

22: } while (fixingHeap && pos != 0);

` 23: }`

For deleting:

1: template <class T>

` 2: T deleteFromHeap(vector<T>* heap) {`

3: int size = heap->size();

4: if (size == 0) {

5: return -1;

` 6: }`

` 7: T ret = heap->front();`

8: if (size == 1) {

` 9: heap->clear();`

10: return ret;

` 11: }`

12: if (size == 2) {

` 13: heap->at(0) = heap->at(size - 1);`

` 14: heap->pop_back();`

15: return ret;

` 16: }`

` 17: heap->at(0) = heap->at(size - 1);`

` 18: heap->pop_back();`

` 19: size--;`

20: bool fixingHeap = true;

21: int pos = 0;

22: do {

23: int child1 = 2 * pos + 1;

24: int child2 = 2 * pos + 2;

25: int switchPosition = 0;

` 26: T max = 0;`

27: if (child2 < size) {

28: //2 children

29: if (heap->at(child1) > heap->at(child2)) {

` 30: switchPosition = child1;`

` 31: max = heap->at(child1);`

` 32: }`

33: else {

` 34: switchPosition = child2;`

` 35: max = heap->at(child2);`

` 36: }`

37: if (heap->at(pos) < max) {

` 38: T temp = heap->at(pos);`

` 39: heap->at(pos) = heap->at(switchPosition);`

` 40: heap->at(switchPosition) = temp;`

` 41: pos = switchPosition;`

42: } else {

43: fixingHeap = false;

` 44: }`

45: } else if (child1 < size) {

46: //1 child

47: if (heap->at(pos) < heap->at(child1)) {

` 48: T temp = heap->at(pos);`

` 49: heap->at(pos) = heap->at(child1);`

` 50: heap->at(child1) = temp;`

` 51: pos = child1;`

52: } else {

53: fixingHeap = false;

` 54: }`

55: } else {

56: //0 children;

57: fixingHeap = false;

` 58: }`

59: } while (fixingHeap);

60: return ret;

` 61: }`

## No comments:

## Post a Comment