use java create node, stack, heap structure (only code)
- User
use java create node, stack, heap structure (only code)
Assistant
// Node for Linked List class ListNode { int data; ListNode next; ListNode(int data) { this.data = data; this.next = null; } } // Node for Binary Tree class TreeNode { int data; TreeNode left; TreeNode right; TreeNode(int data) { this.data = data; this.left = null; this.right = null; } } // Stack Implementation using Array class Stack { private int[] arr; private int top; private int capacity; Stack(int size) { arr = new int[size]; capacity = size; top = -1; } void push(int x) { if (isFull()) { throw new RuntimeException("Stack Overflow"); } arr[++top] = x; } int pop() { if (isEmpty()) { throw new RuntimeException("Stack Underflow"); } return arr[top--]; } int peek() { if (isEmpty()) { throw new RuntimeException("Stack is empty"); } return arr[top]; } boolean isEmpty() { return top == -1; } boolean isFull() { return top == capacity - 1; } } // Stack Implementation using Linked List class LinkedStack { private ListNode top; void push(int x) { ListNode newNode = new ListNode(x); newNode.next = top; top = newNode; } int pop() { if (isEmpty()) { throw new RuntimeException("Stack Underflow"); } int data = top.data; top = top.next; return data; } int peek() { if (isEmpty()) { throw new RuntimeException("Stack is empty"); } return top.data; } boolean isEmpty() { return top == null; } } // Min Heap Implementation class MinHeap { private int[] heap; private int size; private int capacity; MinHeap(int capacity) { this.capacity = capacity; this.size = 0; heap = new int[capacity]; } private int parent(int i) { return (i - 1) / 2; } private int leftChild(int i) { return 2 * i + 1; } private int rightChild(int i) { return 2 * i + 2; } void insert(int key) { if (size == capacity) { throw new RuntimeException("Heap is full"); } heap[size] = key; int current = size; size++; while (current != 0 && heap[parent(current)] > heap[current]) { swap(current, parent(current)); current = parent(current); } } int extractMin() { if (size <= 0) { throw new RuntimeException("Heap is empty"); } if (size == 1) { size--; return heap[0]; } int root = heap[0]; heap[0] = heap[size - 1]; size--; minHeapify(0); return root; } void minHeapify(int i) { int left = leftChild(i); int right = rightChild(i); int smallest = i; if (left < size && heap[left] < heap[smallest]) { smallest = left; } if (right < size && heap[right] < heap[smallest]) { smallest = right; } if (smallest != i) { swap(i, smallest); minHeapify(smallest); } } private void swap(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } int getMin() { if (size <= 0) { throw new RuntimeException("Heap is empty"); } return heap[0]; } } // Max Heap Implementation class MaxHeap { private int[] heap; private int size; private int capacity; MaxHeap(int capacity) { this.capacity = capacity; this.size = 0; heap = new int[capacity]; } private int parent(int i) { return (i - 1) / 2; } private int leftChild(int i) { return 2 * i + 1; } private int rightChild(int i) { return 2 * i + 2; } void insert(int key) { if (size == capacity) { throw new RuntimeException("Heap is full"); } heap[size] = key; int current = size; size++; while (current != 0 && heap[parent(current)] < heap[current]) { swap(current, parent(current)); current = parent(current); } } int extractMax() { if (size <= 0) { throw new RuntimeException("Heap is empty"); } if (size == 1) { size--; return heap[0]; } int root = heap[0]; heap[0] = heap[size - 1]; size--; maxHeapify(0); return root; } void maxHeapify(int i) { int left = leftChild(i); int right = rightChild(i); int largest = i; if (left < size && heap[left] > heap[largest]) { largest = left; } if (right < size && heap[right] > heap[largest]) { largest = right; } if (largest != i) { swap(i, largest); maxHeapify(largest); } } private void swap(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } int getMax() { if (size <= 0) { throw new RuntimeException("Heap is empty"); } return heap[0]; } }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.