FilesExpand file tree

 DSA

/

Heap.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

98 lines (74 loc) · 2.07 KB

 DSA

/

Heap.java

Copy path

Top

File metadata and controls

• Code
• Blame

98 lines (74 loc) · 2.07 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

import java.util.ArrayList;

public class Heap<T extends Comparable<T>>{

private ArrayList<T> list;

public Heap(){

list = new ArrayList<>();

}

public void insert(T value){

list.add(value);

upheap(list.size() - 1);

}

public int size(){

return list.size();

}

private void upheap(int index){

if(index == 0){

return;

}

int p = parent(index);

if(list.get(index).compareTo(list.get(p)) < 0){

swap(index, p);

upheap(p);

}

}

public T remove() throws Exception{

if(list.isEmpty()){

throw new Exception("Removing from empty Heap");

}

T temp = list.get(0);

T last = list.remove(list.size() - 1);

if(!list.isEmpty()){

list.set(0, last);

downheap(0);

}

return temp;

}

private void downheap(int index) {

int min = index;

int left = left(index);

int right = right(index);

// check is left < min

if(left < list.size() && list.get(min).compareTo(list.get(left)) > 0){

min = left;

}

// check if right < min

if(right < list.size() && list.get(min).compareTo(list.get(right)) > 0){

min = right;

}

if(min != index){

swap(min, index);

downheap(min);

}

}

private void swap(int first, int second) {

T temp = list.get(first);

list.set(first, list.get(second));

list.set(second, temp);

}

private int parent(int index){

return (index - 1) / 2;

}

private int left(int index){

return index * 2 + 1;

}

private int right(int index){

return index * 2 + 2;

}

public ArrayList<T> heapSort() throws Exception {

ArrayList<T> data = new ArrayList<>();

while(!list.isEmpty()){

data.add(this.remove());

}

return data;

}

}