Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm
The running time of adding a vertex to the independent set $S$ is $O(1)$ if you use an appropriate set data structure, such as a linked list, an array, or a dictionary. Also, deleting a vertex $v$ from $G$ (once you have identified the vertex) takes time proportional to the number of neighbours, which, in this case, is bounded above by a constant ($4$), so it also takes $O(1)$ time.

The running time of your greedy algorithm will, therefore, be dominated by the costs of the maximum-weight vertex computations. I can think of three ways to implement this operation:


Naive approach - $O(|V|)$: identifying the maximum-weight vertex of a graph takes linear time in the number of vertices if you explore all of them.
Priority queue - $O(log \: |V|)$ : since you are doing repeated maximum computations, it makes sense to use a priority queue, which allows you to extract the maximum element in logarithmic time.
Sorted array - $O(1)$ : the maximum-weight vertex of a graph can be identified in constant time if you sort the vertices by weight beforehand.


The number of times that the algorithm computes the maximum-weight vertex is equal to the number of iterations, which is $O(|V|)$. Therefore, the naive approach takes $O(|V|^2)$ time and the priority queue based solution takes $O(|V| \: log \: |V|)$ time. In the sorting-based solution, each iteration takes $O(1)$ time; however, the overall running time is not $O(|V|)$, but, rather, $O(|V| \: log \: |V|)$ because the running time is dominated by the sorting operation.